Copertina

A simple Path-based LP Relaxation for Directed Steiner Tree

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Pashkovich, Kanstantsin, Pozzi, Marta, Sanità, Laura
Natura:	Preprint
Pubblicazione:	2026
Soggetti:	Data Structures and Algorithms Primary: 90C27 Secondary: 68W25, 90C05
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

A Speed-up for Helsgaun's TSP Heuristic by Relaxing the Positive Gain Criterion
di: Ammann, Sabrina C. L., et al.
Pubblicazione: (2024)

A $5$-Approximation Analysis for the Cover Small Cuts Problem
di: Simmons, Miles, et al.
Pubblicazione: (2026)

Improved Approximation Algorithms for Capacitated Network Design and Flexible Graph Connectivity
di: Bansal, Ishan, et al.
Pubblicazione: (2024)

Improved Regret Guarantees for Online Mirror Descent using a Portfolio of Mirror Maps
di: Gupta, Swati, et al.
Pubblicazione: (2026)

Deterministic Algorithm and Faster Algorithm for Submodular Maximization subject to a Matroid Constraint
di: Buchbinder, Niv, et al.
Pubblicazione: (2024)

Loss Minimization for Electrical Flows over Spanning Trees on Grids
di: Ito, Takehiro, et al.
Pubblicazione: (2024)

New Theoretical Insights and Algorithmic Solutions for Reconstructing Score Sequences from Tournament Score Sets
di: Liu, Bowen
Pubblicazione: (2025)

Submodular Maximization over a Matroid $k$-Intersection: Multiplicative Improvement over Greedy
di: Feldman, Moran, et al.
Pubblicazione: (2026)

Supermodular Maximization with Cardinality Constraints
di: Chen, Xujin, et al.
Pubblicazione: (2025)

Improved Integrality Gap in Max-Min Allocation: or Topology at the North Pole
di: Haxell, Penny, et al.
Pubblicazione: (2022)

Improved Approximation Algorithms for Path and Forest Augmentation via a Novel Relaxation
di: Hommelsheim, Felix
Pubblicazione: (2025)

On the on-line coloring of unit interval graphs with proper interval representation
di: Curbelo, Israel R., et al.
Pubblicazione: (2024)

Optimal Online Bipartite Matching in Degree-2 Graphs
di: Bhangale, Amey, et al.
Pubblicazione: (2025)

An improved approximation algorithm for k-Median
di: Young, Neal E.
Pubblicazione: (2025)

A note on the parameter $\ell$ in Buchbinder--Feldman's deterministic submodular matroid algorithm
di: Li, Shisheng
Pubblicazione: (2026)

Bicriteria Submodular Maximization
di: Feldman, Moran, et al.
Pubblicazione: (2025)

The Complexity Landscape of Two-Stage Robust Selection Problems with Budgeted Uncertainty
di: Goerigk, Marc, et al.
Pubblicazione: (2026)

Advancing Stochastic 3-SAT Solvers by Dissipating Oversatisfied Constraints
di: Schwardt, J., et al.
Pubblicazione: (2025)

Approximation algorithms for the prize-collecting rural postman problem
di: Li, Hong, et al.
Pubblicazione: (2026)

Approximating Graphic Multi-Path TSP and Graphic Ordered TSP
di: Alimi, Morteza, et al.
Pubblicazione: (2025)

Revisiting Chazelle's Implementation of the Bottom-Left Heuristic: A Corrected and Rigorous Analysis
di: Michel, Stefan
Pubblicazione: (2025)

Assignment-Routing Optimization with Cutting-Plane Subtour Elimination: Solver and Benchmark Dataset
di: Yuan, Qilong
Pubblicazione: (2025)

Covering and packing mixed-integer linear programs with a fixed number of constraints: Approximation and convex hull
di: Grobben, Kobe, et al.
Pubblicazione: (2025)

Zero-free regions of partition functions with applications to algorithms and graph limits
di: Regts, Guus
Pubblicazione: (2015)

Critical Relaxed-Stable Matchings with Ties in the Many-to-Many Setting
di: Nasre, Meghana, et al.
Pubblicazione: (2023)

Totally $Δ$-Modular Tree Decompositions of Graphic Matrices for Integer Programming
di: McFarland, Caleb
Pubblicazione: (2026)

A Fast Monte Carlo algorithm for evaluating matrix functions with application in complex networks
di: Guidotti, Nicolas L., et al.
Pubblicazione: (2023)

A $4/3$ Approximation for $2$-Vertex-Connectivity
di: Bosch-Calvo, Miguel, et al.
Pubblicazione: (2023)

On the boundedness of the sequence generated by minibatch stochastic gradient descent
di: Bauschke, Heinz H., et al.
Pubblicazione: (2025)

Symmetric Submodular Functions, Uncrossable Functions, and Structural Submodularity
di: Simmons, Miles, et al.
Pubblicazione: (2025)

Extending Exact Integrality Gap Computations for the Metric TSP
di: Cook, William, et al.
Pubblicazione: (2026)

On the PLS-Completeness of $k$-Opt Local Search for the Traveling Salesman Problem
di: Heimann, Sophia, et al.
Pubblicazione: (2026)

Distributed Computing for Huge-Scale Aggregative Convex Programming
di: Tao, Luoyi
Pubblicazione: (2026)

Finding Short Paths on Simple Polytopes
di: Black, Alexander E., et al.
Pubblicazione: (2026)

Young domination on Hamming rectangles
di: Gravner, Janko, et al.
Pubblicazione: (2025)

A $5/4$-Approximation for Two-Edge Connectivity
di: Bosch-Calvo, Miguel, et al.
Pubblicazione: (2024)

Tighter Approximation for the Uniform Cost-Distance Steiner Tree Problem
di: Foos, Josefine, et al.
Pubblicazione: (2023)

Exact Dynamic Programming for Solow--Polasky Diversity Subset Selection on Lines and Staircases
di: Emmerich, Michael T. M.
Pubblicazione: (2026)

A Fast 3-Approximation for the Capacitated Tree Cover Problem with Edge Loads
di: Rockel-Wolff, Benjamin
Pubblicazione: (2024)

A near-complete resolution of the exponential-time complexity of k-opt for the traveling salesman problem
di: Heimann, Sophia, et al.
Pubblicazione: (2025)