Greedy algorithms for steiner forest

Anupam Gupta, Amit Kumar

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publicationSTOC 2015 - Proceedings of the 2015 ACM Symposium on Theory of Computing
PublisherAssociation for Computing Machinery
Pages871-878
Number of pages8
ISBN (Electronic)9781450335362
DOIs
StatePublished - Jun 14 2015
Event47th Annual ACM Symposium on Theory of Computing, STOC 2015 - Portland, United States
Duration: Jun 14 2015Jun 17 2015

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
Volume14-17-June-2015
ISSN (Print)0737-8017

Other

Other47th Annual ACM Symposium on Theory of Computing, STOC 2015
Country/TerritoryUnited States
CityPortland
Period6/14/156/17/15

ASJC Scopus subject areas

  • Software

Fingerprint

Dive into the research topics of 'Greedy algorithms for steiner forest'. Together they form a unique fingerprint.

Cite this