A local-search algorithm for Steiner forest
From MaRDI portal
Abstract: In the Steiner Forest problem, we are given a graph and a collection of source-sink pairs, and the goal is to find a subgraph of minimum total length such that all pairs are connected. The problem is APX-Hard and can be 2-approximated by, e.g., the elegant primal-dual algorithm of Agrawal, Klein, and Ravi from 1995. We give a local-search-based constant-factor approximation for the problem. Local search brings in new techniques to an area that has for long not seen any improvements and might be a step towards a combinatorial algorithm for the more general survivable network design problem. Moreover, local search was an essential tool to tackle the dynamic MST/Steiner Tree problem, whereas dynamic Steiner Forest is still wide open. It is easy to see that any constant factor local search algorithm requires steps that add/drop many edges together. We propose natural local moves which, at each step, either (a) add a shortest path in the current graph and then drop a bunch of inessential edges, or (b) add a set of edges to the current solution. This second type of moves is motivated by the potential function we use to measure progress, combining the cost of the solution with a penalty for each connected component. Our carefully-chosen local moves and potential function work in tandem to eliminate bad local minima that arise when using more traditional local moves.
Recommendations
- Fast local search for Steiner trees in graphs
- Elementary Approximation Algorithms for Prize Collecting Steiner Tree Problems
- Fast local search for the Steiner problem in graphs
- Elementary approximation algorithms for prize collecting Steiner tree problems
- A primal-dual approximation algorithm for the Steiner forest problem
Cites work
- A factor 2 approximation algorithm for the generalized Steiner network problem
- A General Approximation Technique for Constrained Forest Problems
- A Group-Strategyproof Cost Sharing Mechanism for the Steiner Forest Game
- A group-strategyproof mechanism for Steiner forests
- A local search approximation algorithm for \(k\)-means clustering
- An Effective Heuristic Algorithm for the Traveling-Salesman Problem
- An effective implementation of the Lin-Kernighan traveling salesman heuristic
- Analysis of a Local Search Heuristic for Facility Location Problems
- Approximate integer decompositions for undirected network design problems
- Approximating the Minimum-Degree Steiner Tree to within One of Optimal
- Constructions for cubic graphs with large girth
- Designing network protocols for good equilibria
- Dynamic Steiner Tree Problem
- Effectiveness of local search for geometric optimization
- Greedy algorithms for Steiner forest
- scientific article; zbMATH DE number 1305098 (Why is no real title available?)
- Local Search Heuristics for k-Median and Facility Location Problems
- Local-search based approximation algorithms for mobile facility location problems (extended abstract)
- On Syntactic versus Computational Views of Approximability
- Online Steiner tree with deletions
- Quasi-polynomial local search for restricted max-min fair allocation
- Saving an epsilon: a 2-approximation for the k-MST problem in graphs
- Simple PTAS's for families of graphs excluding a minor
- The design of approximation algorithms
- The power of deferral: maintaining a constant-competitive Steiner tree online
- The Power of Dynamic Distance Oracles
- The power of recourse for online MST and TSP
- When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks
Cited in
(11)- Parallel local search for Steiner trees in graphs
- Stronger MIP formulations for the Steiner forest problem
- Approximation of Steiner forest via the bidirected cut relaxation
- Algorithms for Forest Local Similarity
- An Exact Algorithm for the Steiner Forest Problem
- On the Complexity of Local Graph Transformations
- Algorithms and Computation
- Approximation algorithms for Steiner forest: An experimental study
- Robust Algorithms for TSP and Steiner Tree
- Robust algorithms for TSP and Steiner tree
- Streaming algorithms for geometric Steiner forest
This page was built for publication: A local-search algorithm for Steiner forest
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4993295)
