Theory Talk by Neil Olver, MIT
Date
–
Host: Nick Harvey
Title: Matroids and Integrality Gaps for Hypergraphic Steiner Tree Relaxations
Abstract: Until recently, LP relaxations have only played a very limited role in the design of approximation algorithms for the Steiner tree problem. This changed when Byrka, Grandoni, Rothvoss and Sanità demonstrated a ln(4) approximation algorithm based on a component-based relaxation (one of a family of "hypergraphic" relaxations). Surprisingly, even though their approach is LP based, they do not obtain a matching bound on the integrality gap, showing only a weaker 1.55 bound by other methods.
We show that indeed the integrality gap is bounded by ln(4). In the process, we obtain a much better structural understanding of these hypergraphic LPs, as well as more efficient and simpler algorithms. Techniques from the theory of matroids and submodular functions play a crucial role.
(Joint work with Michel Goemans, Thomas Rothvoss and Rico Zenklusen.)