Imagen de Portada

On the Bidirected Cut Relaxation for Steiner Forest

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Byrka, Jarosław, Grandoni, Fabrizio, Traub, Vera
Formato:	Preprint
Publicado:	2024
Materias:	Data Structures and Algorithms Discrete Mathematics
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

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

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

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

Terminal Steiner tree problem : Complexity and Algorithms
por: S, Jyothish, et al.
Publicado: (2026)

Bicriterial Approximation for the Incremental Prize-Collecting Steiner-Tree Problem
por: Disser, Yann, et al.
Publicado: (2024)

An approximation algorithm for Maximum DiCut vs. Cut
por: Nakajima, Tamio-Vesa, et al.
Publicado: (2024)

Steiner Forest for $H$-Subgraph-Free Graphs
por: Eagling-Vose, Tala, et al.
Publicado: (2026)

The Parameterized Complexity Landscape of Two-Sets Cut-Uncut
por: Bentert, Matthias, et al.
Publicado: (2024)

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

Cuts in Graphs with Matroid Constraints
por: Banik, Aritra, et al.
Publicado: (2024)

Cuts and Gauges for Submodular Width
por: Lanzinger, Matthias
Publicado: (2026)

EPTAS for Hard Graph Cut Problems for Dense Graphs
por: Deguchi, Kaisei, et al.
Publicado: (2026)

Thin Trees via $k$-Respecting Cut Identities
por: Daga, Mohit
Publicado: (2025)

Towards the Characterization of Terminal Cut Functions: a Condition for Laminar Families
por: Chen, Yu, et al.
Publicado: (2023)

Boosting Rectilinear Steiner Minimum Tree Algorithms with Augmented Bounding Volume Hierarchy
por: Yang, Puhan, et al.
Publicado: (2025)

Sampling Balanced Forests of Grids in Polynomial Time
por: Cannon, Sarah, et al.
Publicado: (2023)

Edge Multiway Cut and Node Multiway Cut are NP-complete on subcubic graphs
por: Johnson, Matthew, et al.
Publicado: (2022)

Deterministic Minimum Steiner Cut in Maximum Flow Time
por: Ding, Matthew, et al.
Publicado: (2023)

Asymptotically Optimal Inapproximability of Maxmin $k$-Cut Reconfiguration
por: Hirahara, Shuichi, et al.
Publicado: (2024)

Multi-Pass Streaming Lower Bounds for Approximating Max-Cut
por: Fei, Yumou, et al.
Publicado: (2025)

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

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

New Sequence-Independent Lifting Techniques for Cutting Planes and When They Induce Facets
por: Prasad, Siddharth, et al.
Publicado: (2024)

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

From Tutte to Floater and Gotsman: On the Resolution of Planar Straight-line Drawings and Morphs
por: Di Battista, Giuseppe, et al.
Publicado: (2021)

A Primal-Dual Extension of the Goemans--Williamson Algorithm for the Weighted Fractional Cut-Covering Problem
por: Proença, Nathan Benedetto, et al.
Publicado: (2023)

Generalized Cuts and Grothendieck Covers: a Primal-Dual Approximation Framework Extending the Goemans--Williamson Algorithm
por: Proença, Nathan Benedetto, et al.
Publicado: (2024)

U-Bubble Model for Mixed Unit Interval Graphs and its Applications: The MaxCut Problem Revisited
por: Kratochvíl, Jan, et al.
Publicado: (2020)

Learning to Prune Instances of Steiner Tree Problem in Graphs
por: Zhang, Jiwei, et al.
Publicado: (2022)

Streaming algorithm for balance gain and cost with cardinality constraint on the integer lattice
por: Tan, Jingjing
Publicado: (2024)

A Lower Bound on the Competitive Ratio of the Permutation Algorithm for Online Facility Assignment on a Line
por: Harada, Tsubasa
Publicado: (2024)

Exponential Time Approximation for Coloring 3-Colorable Graphs
por: Guruswami, Venkatesan, et al.
Publicado: (2024)

Generation of weighted trees, block trees and block graphs
por: Ekim, Tınaz, et al.
Publicado: (2024)

Circular-arc graphs and the Helly property
por: Derbisz, Jan, et al.
Publicado: (2024)

Parameterized Saga of First-Fit and Last-Fit Coloring
por: Agrawal, Akanksha, et al.
Publicado: (2024)

Detecting Disjoint Shortest Paths in Linear Time and More
por: Akmal, Shyan, et al.
Publicado: (2024)

Approximation Algorithm of Minimum All-Ones Problem for Arbitrary Graphs
por: Wang, Chen, et al.
Publicado: (2024)

A Nearly Optimal Deterministic Algorithm for Online Transportation Problem
por: Harada, Tsubasa, et al.
Publicado: (2024)

Deterministic counting from coupling independence
por: Chen, Xiaoyu, et al.
Publicado: (2024)

Stability in Graphs with Matroid Constraints
por: Fomin, Fedor V., et al.
Publicado: (2024)