Buchumschlag

The Bidirected Cut Relaxation for Steiner Tree has Integrality Gap Smaller than 2

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Byrka, Jarosław, Grandoni, Fabrizio, Traub, Vera
Format:	Preprint
Veröffentlicht:	2024
Schlagworte:	Data Structures and Algorithms Discrete Mathematics
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

On the Bidirected Cut Relaxation for Steiner Forest
von: Byrka, Jarosław, et al.
Veröffentlicht: (2024)

The Bidirected Cut Relaxation for Steiner Tree: Better Integrality Gap Bounds and the Limits of Moat Growing
von: Paschmanns, Paul, et al.
Veröffentlicht: (2026)

Unsplittable Cost Flows from Unweighted Error-Bounded Variants
von: Swamy, Chaitanya, et al.
Veröffentlicht: (2025)

Bicriterial Approximation for the Incremental Prize-Collecting Steiner-Tree Problem
von: Disser, Yann, et al.
Veröffentlicht: (2024)

Terminal Steiner tree problem : Complexity and Algorithms
von: S, Jyothish, et al.
Veröffentlicht: (2026)

An approximation algorithm for Maximum DiCut vs. Cut
von: Nakajima, Tamio-Vesa, et al.
Veröffentlicht: (2024)

Path Contraction Faster than $2^n$
von: Agrawal, Akanksha, et al.
Veröffentlicht: (2025)

The Parameterized Complexity Landscape of Two-Sets Cut-Uncut
von: Bentert, Matthias, et al.
Veröffentlicht: (2024)

Thin Trees via $k$-Respecting Cut Identities
von: Daga, Mohit
Veröffentlicht: (2025)

An $Ω(n \log n)$ Randomized Lower Bound for Cutting a Cake into Proportionally Fair Pieces
von: Arndt, Stephen, et al.
Veröffentlicht: (2026)

Boosting Rectilinear Steiner Minimum Tree Algorithms with Augmented Bounding Volume Hierarchy
von: Yang, Puhan, et al.
Veröffentlicht: (2025)

Cuts in Graphs with Matroid Constraints
von: Banik, Aritra, et al.
Veröffentlicht: (2024)

Cuts and Gauges for Submodular Width
von: Lanzinger, Matthias
Veröffentlicht: (2026)

EPTAS for Hard Graph Cut Problems for Dense Graphs
von: Deguchi, Kaisei, et al.
Veröffentlicht: (2026)

Towards the Characterization of Terminal Cut Functions: a Condition for Laminar Families
von: Chen, Yu, et al.
Veröffentlicht: (2023)

Deterministic approximate counting of colorings with fewer than $2Δ$ colors via absence of zeros
von: Bencs, Ferenc, et al.
Veröffentlicht: (2024)

Edge Multiway Cut and Node Multiway Cut are NP-complete on subcubic graphs
von: Johnson, Matthew, et al.
Veröffentlicht: (2022)

Deterministic Minimum Steiner Cut in Maximum Flow Time
von: Ding, Matthew, et al.
Veröffentlicht: (2023)

Steiner Forest for $H$-Subgraph-Free Graphs
von: Eagling-Vose, Tala, et al.
Veröffentlicht: (2026)

A Structural Equivalence of Symmetric TSP to a Constrained Group Steiner Tree Problem
von: Arslanoğlu, Yılmaz
Veröffentlicht: (2026)

Simultaneous Drawing of Layered Trees
von: Katheder, Julia, et al.
Veröffentlicht: (2023)

Freeze-Tag in $L_1$ has Wake-up Time Five
von: Bonichon, Nicolas, et al.
Veröffentlicht: (2024)

Learning to Prune Instances of Steiner Tree Problem in Graphs
von: Zhang, Jiwei, et al.
Veröffentlicht: (2022)

Polynomial Kernels for Spanning Tree with Diversity Requirements
von: Golovach, Petr A., et al.
Veröffentlicht: (2026)

Optimal Generation of Strictly Increasing Binary Trees and Beyond
von: Bodini, Olivier, et al.
Veröffentlicht: (2024)

Approximation of Spanning Tree Congestion using Hereditary Bisection
von: Kolman, Petr
Veröffentlicht: (2024)

Revisiting Tree Isomorphism: An Algorithmic Bric-à-Brac
von: Ingels, Florian
Veröffentlicht: (2023)

Algorithms and Hardness for Geodetic Set on Tree-like Digraphs
von: Foucaud, Florent, et al.
Veröffentlicht: (2026)

Efficient Algorithms for Interdicting Facilities in Trees and Bounded Treewidth Graphs
von: Abbasi, Ali, et al.
Veröffentlicht: (2026)

Pattern-Sparse Tree Decompositions in $H$-Minor-Free Graphs
von: Marx, Dániel, et al.
Veröffentlicht: (2026)

Optimal Mixing via Tensorization for Random Independent Sets on Arbitrary Trees
von: Efthymiou, Charilaos, et al.
Veröffentlicht: (2023)

Asymptotically Optimal Inapproximability of Maxmin $k$-Cut Reconfiguration
von: Hirahara, Shuichi, et al.
Veröffentlicht: (2024)

Triangle-free 2-matchings
von: Paluch, Katarzyna
Veröffentlicht: (2023)

On the Structural Parameterizations of 2-Club with Triangle Constraints
von: Jacob, Ashwin, et al.
Veröffentlicht: (2025)

Multi-Pass Streaming Lower Bounds for Approximating Max-Cut
von: Fei, Yumou, et al.
Veröffentlicht: (2025)

Approximating Maximum Edge 2-Coloring by Normalizing Graphs
von: Mömke, Tobias, et al.
Veröffentlicht: (2024)

Finding perfect matchings in bridgeless cubic multigraphs without dynamic (2-)connectivity
von: Gawrychowski, Paweł, et al.
Veröffentlicht: (2024)

Near-Optimal Constructive Bounds for $\ell_2$ Prefix Discrepancy and Steinitz Problems via Affine Spectral Independence
von: Dutta, Kunal, et al.
Veröffentlicht: (2026)

Maximum Biclique for Star 1,2,3 -free and Bounded Bimodularwidth Twin-free Bipartite Graphs $\star$
von: de Montgolfier, Fabien, et al.
Veröffentlicht: (2025)

Linear-Time MaxCut in Multigraphs Parameterized Above the Poljak-Turzík Bound
von: Lill, Jonas, et al.
Veröffentlicht: (2024)