Matroids and Integrality Gaps for Hypergraphic Steiner Tree Relaxations

Michel X. Goemans, Neil Olver, Thomas Rothvoss +1

Until recently, LP relaxations have played a limited role in the design of approximation algorithms for the Steiner tree problem. In 2010, Byrka et al. presented a ln(4)+epsilon ap…