TY - GEN

T1 - Greedy algorithms for steiner forest

AU - Gupta, Anupam

AU - Kumar, Amit

N1 - Publisher Copyright:
© Copyright 2015 ACM.

PY - 2015/6/14

Y1 - 2015/6/14

N2 - In the Steiner Forest problem, we are given terminal pairs {si,ti}, and need to find the cheapest subgraph which connects each of the terminal pairs together. In 1991, Agrawal, Klein, and Ravi gave a primal-dual constant-factor approximation algorithm for this problem. Until this work, the only constant-factor approximations we know are via linear programming relaxations. In this paper, we consider the following greedy algorithm: Given terminal pairs in a metric space, a terminal is active if its distance to its partner is non-zero. Pick the two closest active terminals (say si,tj), set the distance between them to zero, and buy a path connecting them. Recompute the metric, and repeat. It has long been open to analyze this greedy algorithm. Our main result shows that this algorithm is a constant-factor approximation. We use this algorithm to give new, simpler constructions of cost-sharing schemes for Steiner forest. In particular, the first "strict" cost-shares for this problem implies a very simple combinatorial sampling-based algorithm for stochastic Steiner forest.

AB - In the Steiner Forest problem, we are given terminal pairs {si,ti}, and need to find the cheapest subgraph which connects each of the terminal pairs together. In 1991, Agrawal, Klein, and Ravi gave a primal-dual constant-factor approximation algorithm for this problem. Until this work, the only constant-factor approximations we know are via linear programming relaxations. In this paper, we consider the following greedy algorithm: Given terminal pairs in a metric space, a terminal is active if its distance to its partner is non-zero. Pick the two closest active terminals (say si,tj), set the distance between them to zero, and buy a path connecting them. Recompute the metric, and repeat. It has long been open to analyze this greedy algorithm. Our main result shows that this algorithm is a constant-factor approximation. We use this algorithm to give new, simpler constructions of cost-sharing schemes for Steiner forest. In particular, the first "strict" cost-shares for this problem implies a very simple combinatorial sampling-based algorithm for stochastic Steiner forest.

UR - http://www.scopus.com/inward/record.url?scp=84958761847&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84958761847&partnerID=8YFLogxK

U2 - 10.1145/2746539.2746590

DO - 10.1145/2746539.2746590

M3 - Conference contribution

AN - SCOPUS:84958761847

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 871

EP - 878

BT - STOC 2015 - Proceedings of the 2015 ACM Symposium on Theory of Computing

PB - Association for Computing Machinery

T2 - 47th Annual ACM Symposium on Theory of Computing, STOC 2015

Y2 - 14 June 2015 through 17 June 2015

ER -