Efficient Algorithms for Solving Hypergraphic Steiner Tree Relaxations in Quasi-Bipartite Instances

Details Efficient Algorithms for Solving Hypergraphic Steiner Tree Relaxations in Quasi-Bipartite Instances Efficient Algorithms for Solving Hypergraphic Steiner Tree Relaxations in Quasi-Bipartite Instances

2012-02-22

arxiv.org/abs/1202.5049v1

Computer Science

Discrete Mathematics

15 pages, 2 figures

Scientific paper

We consider the Steiner tree problem in quasi-bipartite graphs, where no two Steiner vertices are connected by an edge. For this class of instances, we present an efficient algorithm to exactly solve the so called directed component relaxation (DCR), a specific form of hypergraphic LP relaxation that was instrumental in the recent break-through result by Byrka et al. [BGRS10] (STOC 2010). Our algorithm hinges on an efficiently computable map from extreme points of the bidirected cut relaxation to feasible solutions of (DCR). As a consequence, together with [BGRS10] we immediately obtain an efficient 73/60-approximation for quasi-bipartite Steiner tree instances. We also present a particularly simple (BCR)-based random sampling algorithm that achieves a performance guarantee slightly better than 77/60.

Affiliated with

Also associated with

No associations

Rating

Efficient Algorithms for Solving Hypergraphic Steiner Tree Relaxations in Quasi-Bipartite Instances 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 Efficient Algorithms for Solving Hypergraphic Steiner Tree Relaxations in Quasi-Bipartite Instances, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient Algorithms for Solving Hypergraphic Steiner Tree Relaxations in Quasi-Bipartite Instances will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-657935