Greedy Algorithms for Steiner Forest. Gupta, A. & Kumar, A. arXiv:1412.7693 [cs], December, 2014. arXiv: 1412.7693
In the Steiner Forest problem, we are given terminal pairs \${\textbackslash}\{s_i, t_i{\textbackslash}\}\$, and need to find the cheapest subgraph which connects each of the terminal pairs together. In 1991, Agrawal, Klein, and Ravi, and Goemans and Williamson gave primal-dual constant-factor approximation algorithms for this problem; until now, the only constant-factor approximations we know are via linear programming relaxations. We consider the following greedy algorithm: Given terminal pairs in a metric space, call a terminal "active" if its distance to its partner is non-zero. Pick the two closest active terminals (say \$s_i, t_j\$), set the distance between them to zero, and buy a path connecting them. Recompute the metric, and repeat. Our main result is that this algorithm is a constant-factor approximation. We also use this algorithm to give new, simpler constructions of cost-sharing schemes for Steiner forest. In particular, the first "group-strict" cost-shares for this problem implies a very simple combinatorial sampling-based algorithm for stochastic Steiner forest.
@article{gupta_greedy_2014,
title = {Greedy {Algorithms} for {Steiner} {Forest}},
url = {http://arxiv.org/abs/1412.7693},
abstract = {In the Steiner Forest problem, we are given terminal pairs \${\textbackslash}\{s\_i, t\_i{\textbackslash}\}\$, and need to find the cheapest subgraph which connects each of the terminal pairs together. In 1991, Agrawal, Klein, and Ravi, and Goemans and Williamson gave primal-dual constant-factor approximation algorithms for this problem; until now, the only constant-factor approximations we know are via linear programming relaxations. We consider the following greedy algorithm: Given terminal pairs in a metric space, call a terminal "active" if its distance to its partner is non-zero. Pick the two closest active terminals (say \$s\_i, t\_j\$), set the distance between them to zero, and buy a path connecting them. Recompute the metric, and repeat. Our main result is that this algorithm is a constant-factor approximation. We also use this algorithm to give new, simpler constructions of cost-sharing schemes for Steiner forest. In particular, the first "group-strict" cost-shares for this problem implies a very simple combinatorial sampling-based algorithm for stochastic Steiner forest.},
urldate = {2015-05-27TZ},
journal = {arXiv:1412.7693 [cs]},
author = {Gupta, Anupam and Kumar, Amit},
month = dec,
year = {2014},
note = {arXiv: 1412.7693},
keywords = {Computer Science - Data Structures and Algorithms}
}