Copertina

The Bidirected Cut Relaxation for Steiner Tree: Better Integrality Gap Bounds and the Limits of Moat Growing

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Paschmanns, Paul, Traub, Vera
Natura:	Preprint
Pubblicazione:	2026
Soggetti:	Data Structures and Algorithms
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

The Bidirected Cut Relaxation for Steiner Tree has Integrality Gap Smaller than 2
di: Byrka, Jarosław, et al.
Pubblicazione: (2024)

On the Bidirected Cut Relaxation for Steiner Forest
di: Byrka, Jarosław, et al.
Pubblicazione: (2024)

Steiner Forest: A Simplified Better-Than-2 Approximation
di: Gupta, Anupam, et al.
Pubblicazione: (2025)

Approximating Asymmetric A Priori TSP beyond the Adaptivity Gap
di: Christalla, Manuel, et al.
Pubblicazione: (2025)

The Days On Days Off Scheduling Problem
di: Nießen, Fabien, et al.
Pubblicazione: (2024)

Minimum+1 Steiner Cuts and Dual Edge Sensitivity Oracle: Bridging the Gap between Global cut and (s,t)-cut
di: Bhanja, Koustav
Pubblicazione: (2024)

Approximation Schemes for Planar Graph Connectivity Problems
di: Neuwohner, Meike, et al.
Pubblicazione: (2025)

Improved Upper Bounds for the Directed Flow-Cut Gap
di: Bodwin, Greg, et al.
Pubblicazione: (2026)

Sublinear Metric Steiner Tree via Improved Bounds for Set Cover
di: Mahabadi, Sepideh, et al.
Pubblicazione: (2024)

Unsplittable Cost Flows from Unweighted Error-Bounded Variants
di: Swamy, Chaitanya, et al.
Pubblicazione: (2025)

Lower Bounds on Flow Sparsifiers with Steiner Nodes
di: Chen, Yu, et al.
Pubblicazione: (2026)

Lower Bounds on $0$-Extension with Steiner Nodes
di: Chen, Yu, et al.
Pubblicazione: (2024)

Parameterized Algorithms for Steiner Forest in Bounded Width Graphs
di: Feldmann, Andreas Emil, et al.
Pubblicazione: (2024)

From Directed Steiner Tree to Directed Polymatroid Steiner Tree in Planar Graphs
di: Chekuri, Chandra, et al.
Pubblicazione: (2024)

Multi-Level Steiner Trees
di: Ahmed, Reyan, et al.
Pubblicazione: (2018)

The Steiner Shortest Path Tree Problem
di: Asher, Omer, et al.
Pubblicazione: (2025)

Tight Lower Bounds for Directed Cut Sparsification and Distributed Min-Cut
di: Cheng, Yu, et al.
Pubblicazione: (2024)

Query Complexity of the Metric Steiner Tree Problem
di: Chen, Yu, et al.
Pubblicazione: (2022)

Prize-Collecting Steiner Tree: A 1.79 Approximation
di: Ahmadi, Ali, et al.
Pubblicazione: (2024)

Cost-Distance Steiner Trees for Timing-Constrained Global Routing
di: Held, Stephan, et al.
Pubblicazione: (2025)

Online Steiner Forest with Recourse
di: Long, Yaowei, et al.
Pubblicazione: (2026)

Almost-Tight Bounds on Preserving Cuts in Classes of Submodular Hypergraphs
di: Khanna, Sanjeev, et al.
Pubblicazione: (2024)

The Steiner Path Aggregation Problem
di: Chen, Da Qi, et al.
Pubblicazione: (2025)

Vehicle Routing with Time-Dependent Travel Times: Theory, Practice, and Benchmarks
di: Blauth, Jannis, et al.
Pubblicazione: (2022)

Flow-weighted Layered Metric Euclidean Capacitated Steiner Tree Problem
di: Bläsius, Thomas, et al.
Pubblicazione: (2025)

Oblivious Algorithms for Maximum Directed Cut: New Upper and Lower Bounds
di: Hwang, Samuel, et al.
Pubblicazione: (2024)

DAG Covers: The Steiner Point Effect
di: Bhore, Sujoy, et al.
Pubblicazione: (2026)

Approximation Algorithms for Steiner Connectivity Augmentation
di: Hathcock, Daniel, et al.
Pubblicazione: (2023)

Optimal Sensitivity Oracle for Steiner Mincut
di: Bhanja, Koustav
Pubblicazione: (2024)

Streaming Algorithms for Geometric Steiner Forest
di: Czumaj, Artur, et al.
Pubblicazione: (2020)

Graph Spanners for Group Steiner Distances
di: Bilò, Davide, et al.
Pubblicazione: (2024)

A Partition-and-Merge Algorithm for Solving the Steiner Tree Problem in Large Graphs
di: Sun, Ming, et al.
Pubblicazione: (2022)

Mind the Gap. Doubling Constant Parametrization of Weighted Problems: TSP, Max-Cut, and More
di: Stoian, Mihail
Pubblicazione: (2026)

Lower Bounds for Adaptive Relaxation-Based Algorithms for Single-Source Shortest Paths
di: Atalig, Sunny, et al.
Pubblicazione: (2024)

Spanners in Planar Domains via Steiner Spanners and non-Steiner Tree Covers
di: Bhore, Sujoy, et al.
Pubblicazione: (2024)

2-Approximation for Prize-Collecting Steiner Forest
di: Ahmadi, Ali, et al.
Pubblicazione: (2023)

Better Diameter Bounds for Efficient Shortcuts and a Structural Criterion for Constructiveness
di: Haeupler, Bernhard, et al.
Pubblicazione: (2026)

Approximation Algorithms for $\ell_p$-Shortest Path and $\ell_p$-Group Steiner Tree
di: Makarychev, Yury, et al.
Pubblicazione: (2024)

Thin Trees for Near Minimum Cuts
di: Klein, Nathan, et al.
Pubblicazione: (2026)

Parameterized Algorithms for the Steiner Arborescence Problem on a Hypercube
di: Mahapatra, Sugyani, et al.
Pubblicazione: (2021)