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 -