@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}
}

{"_id":"ZvXm9bArk9xGLLK4Z","bibbaseid":"gupta-kumar-greedyalgorithmsforsteinerforest-2014","downloads":0,"creationDate":"2016-12-19T20:50:58.200Z","title":"Greedy Algorithms for Steiner Forest","author_short":["Gupta, A.","Kumar, A."],"year":2014,"bibtype":"article","biburl":"http://bibbase.org/zotero/verschae","bibdata":{"bibtype":"article","type":"article","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":[{"propositions":[],"lastnames":["Gupta"],"firstnames":["Anupam"],"suffixes":[]},{"propositions":[],"lastnames":["Kumar"],"firstnames":["Amit"],"suffixes":[]}],"month":"December","year":"2014","note":"arXiv: 1412.7693","keywords":"Computer Science - Data Structures and Algorithms","bibtex":"@article{gupta_greedy_2014,\n\ttitle = {Greedy {Algorithms} for {Steiner} {Forest}},\n\turl = {http://arxiv.org/abs/1412.7693},\n\tabstract = {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.},\n\turldate = {2015-05-27TZ},\n\tjournal = {arXiv:1412.7693 [cs]},\n\tauthor = {Gupta, Anupam and Kumar, Amit},\n\tmonth = dec,\n\tyear = {2014},\n\tnote = {arXiv: 1412.7693},\n\tkeywords = {Computer Science - Data Structures and Algorithms}\n}\n\n","author_short":["Gupta, A.","Kumar, A."],"key":"gupta_greedy_2014","id":"gupta_greedy_2014","bibbaseid":"gupta-kumar-greedyalgorithmsforsteinerforest-2014","role":"author","urls":{"Paper":"http://arxiv.org/abs/1412.7693"},"keyword":["Computer Science - Data Structures and Algorithms"],"downloads":0,"html":""},"search_terms":["greedy","algorithms","steiner","forest","gupta","kumar"],"keywords":["computer science - data structures and algorithms"],"authorIDs":[],"dataSources":["TJDe75XCoX4GYYsBX"]}