Hypergraphic LP Relaxations for Steiner Trees
Deeparnab Chakrabarty, Jochen Könemann, David Pritchard · SIAM Journal on Discrete Mathematics · 2013
In this paper we prove new properties of hypergraphic linear programming relaxations for the Steiner tree problem. In particular, we show that a partition-based relaxation has the same value as other relaxations based on subtours and directed cuts. Additionally, we establish structural properties of basic solutions by using uncrossing methods. For quasi-bipartite instances we show that these hypergraphic relaxations have the same value as the well-studied graphic bidirected cut relaxation. We show how to analyze several approximation algorithms relative to the hypergraphic linear programs; one gives an approximation ratio and integrality gap of at most $\sqrt{3} \simeq 1.729$ for the Steiner tree problem when the full components arrive online.