EUVIMEDEUVIMED entdecken
Crossref

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

Jarosław Byrka, Fabrizio Grandoni, Vera Traub

SIAM Journal on Computing · 31.10.2026 · 55 (5) · FOCS24-487-FOCS24-533

DOI: 10.1137/24m1717725 ↗

Kurz gefasst

Fachartikel in der Zeitschrift SIAM Journal on Computing, online erschienen am 17.09.2026. Verfasst von Jarosław Byrka und 2 weiteren Autor:innen. Die Arbeit nennt 51 Literaturangaben. Gefördert von: Narodowe Centrum Nauki, Schweizerischer Nationalfonds zur Förderung der Wissenschaftlichen Forschung.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

The Steiner tree problem is one of the most prominent problems in network design. Given an edge-weighted undirected graph and a subset of the vertices, called terminals, the task is to compute a minimum-weight tree containing all terminals (and possibly further vertices). The best-known approximation algorithms for Steiner tree involve enumeration of a (polynomial but) very large number of candidate components and are therefore slow in practice. A promising ingredient for the design of fast and accurate approximation algorithms for Steiner tree is the bidirected cut relaxation (BCR): bidirect all edges, choose an arbitrary terminal as a root, and enforce that each cut containing some terminal but not the root has one unit of fractional edges leaving it. BCR is known to be integral in the spanning tree case [Fulkerson’74], i.e., when all the vertices are terminals. For general instances, however, it was not even known whether the integrality gap of BCR is better than the integrality gap of the natural undirected cut relaxation, which is exactly 2. We resolve this question by proving an upper bound of 1.9988 on the integrality gap of BCR.

Förderung

  • Narodowe Centrum Nauki
  • Schweizerischer Nationalfonds zur Förderung der Wissenschaftlichen Forschung

Zitieren

APA

Byrka, J., Grandoni, F., & Traub, V. (2026). The Bidirected Cut Relaxation for Steiner Tree Has Integrality Gap Smaller than 2. SIAM Journal on Computing, 55(5), FOCS24-487-FOCS24-533. https://doi.org/10.1137/24m1717725

Vancouver

Byrka J, Grandoni F, Traub V. The Bidirected Cut Relaxation for Steiner Tree Has Integrality Gap Smaller than 2. SIAM Journal on Computing. 2026;55(5):FOCS24-487-FOCS24-533. doi:10.1137/24m1717725

BibTeX
@article{Byrka2026,
  author = {Byrka, Jarosław and Grandoni, Fabrizio and Traub, Vera},
  title = {The Bidirected Cut Relaxation for Steiner Tree Has Integrality Gap Smaller than 2},
  journal = {SIAM Journal on Computing},
  year = {2026},
  volume = {55},
  number = {5},
  pages = {FOCS24--487--FOCS24--533},
  doi = {10.1137/24m1717725}
}
Kostenlos starten →