Matroids and Integrality Gaps for Hypergraphic Steiner Tree Relaxations

Details Matroids and Integrality Gaps for Hypergraphic Steiner Tree Relaxations Matroids and Integrality Gaps for Hypergraphic Steiner Tree Relaxations

2011-11-30

arxiv.org/abs/1111.7280v2

Computer Science

Discrete Mathematics

Corrects an issue at the end of Section 3. Various other minor improvements to the exposition

Scientific paper

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 approximation based on a hypergraphic LP relaxation, but surprisingly, their analysis does not provide a matching bound on the integrality gap. We take a fresh look at hypergraphic LP relaxations for the Steiner tree problem - one that heavily exploits methods and results from the theory of matroids and submodular functions - which leads to stronger integrality gaps, faster algorithms, and a variety of structural insights of independent interest. More precisely, we present a deterministic ln(4)+epsilon approximation that compares against the LP value and therefore proves a matching ln(4) upper bound on the integrality gap. Similarly to Byrka et al., we iteratively fix one component and update the LP solution. However, whereas they solve an LP at every iteration after contracting a component, we show how feasibility can be maintained by a greedy procedure on a well-chosen matroid. Apart from avoiding the expensive step of solving a hypergraphic LP at each iteration, our algorithm can be analyzed using a simple potential function. This gives an easy means to determine stronger approximation guarantees and integrality gaps when considering restricted graph topologies. In particular, this readily leads to a 73/60 bound on the integrality gap for quasi-bipartite graphs. For the case of quasi-bipartite graphs, we present a simple algorithm to transform an optimal solution to the bidirected cut relaxation to an optimal solution of the hypergraphic relaxation, leading to a fast 73/60 approximation for quasi-bipartite graphs. Furthermore, we show how the separation problem of the hypergraphic relaxation can be solved by computing maximum flows, providing a fast independence oracle for our matroids.

Affiliated with

Also associated with

No associations

Rating

Matroids and Integrality Gaps for Hypergraphic Steiner Tree Relaxations does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Matroids and Integrality Gaps for Hypergraphic Steiner Tree Relaxations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Matroids and Integrality Gaps for Hypergraphic Steiner Tree Relaxations will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-9424