Greedy algorithms for Steiner forest

DOI10.1145/2746539.2746590MaRDI QIDQ2941584zbMATH OpenOpenAlexFDO

Authors Anupam Gupta, Amit Kumar

Publication date 21 August 2015

Published in Proceedings of the forty-seventh annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1412.7693

zbMATH Keywords

approximation algorithmscost sharinggreedySteiner foreststochastic algorithms

Mathematics Subject Classification ID

Trees (05C05) Flows in graphs (05C21) Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Approximation algorithms (68W25)

Abstract: In the Steiner Forest problem, we are given terminal pairs $s_i,t_i$, 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.

Recommendations

• Strict cost sharing schemes for Steiner forest
• A primal-dual approximation algorithm for the Steiner forest problem
• A constant-factor approximation for stochastic Steiner forest
• A group-strategyproof mechanism for Steiner forests
• An approximation algorithm to the \(k\)-Steiner forest problem

Cites work

• Approximate distance oracles
• Approximate distance oracles with constant query time
• Automata, Languages and Programming
• Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error
• Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
• Fast C-K-R partitions of sparse graphs
• Near-Linear Time Construction of Sparse Neighborhood Covers
• On approximate distance labels and routing schemes with affine stretch
• On sparse spanners of weighted graphs
• Ramsey partitions and proximity data structures
• Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem
• Shortest-path queries in static networks

Cited in

(14)

• A greedy heuristic for a minimum-weight forest problem
• Purely combinatorial approximation algorithms for maximum \(k\)-vertex cover in bipartite graphs
• Stronger MIP formulations for the Steiner forest problem
• Approximation of Steiner forest via the bidirected cut relaxation
• Approximation algorithms for stochastic combinatorial optimization problems
• A local-search algorithm for Steiner forest
• An Exact Algorithm for the Steiner Forest Problem
• On the Complexity of Local Graph Transformations
• A constant-factor approximation for stochastic Steiner forest
• A PTAS for the Steiner forest problem in doubling metrics
• Strict cost sharing schemes for Steiner forest
• Approximation algorithms for Steiner forest: An experimental study
• 2-approximation for prize-collecting Steiner forest
• Streaming algorithms for geometric Steiner forest

Describes a project that uses

Uses Software

• Graphs

This page was built for publication: Greedy algorithms for Steiner forest

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2941584)