15 października 2024 11:15
[Seminarium ZOK] Jarek Byrka: The Bidirected Cut Relaxation for Steiner Tree has Integrality Gap Smaller than 2
Abstract:
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 [Edmonds'67], 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 relaxation, which is exactly
2. We resolve this question by proving an upper bound of 1.9988 on the
integrality gap of BCR.
Joint work with Fabrizio Grandoni and Vera Traub.