A Local-Search Algorithm for Steiner Forest

DOI10.4230/LIPIcs.ITCS.2018.31zbMath1462.68140arXiv1707.02753OpenAlexW2963996640MaRDI QIDQ4993295

Jannik Matuschke, Melanie Schmidt, Anupam Gupta, José Verschae, Amit Kumar, Daniel R. Schmidt, Martin Groß

Publication date: 15 June 2021

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

zbMATH Keywords

local searchnetwork designapproximation algorithmsSteiner forest

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Related Items

Approximation algorithms for Steiner forest: An experimental study, Robust Algorithms for TSP and Steiner Tree, Stronger MIP formulations for the Steiner forest problem, An Exact Algorithm for the Steiner Forest Problem, Approximation of Steiner forest via the bidirected cut relaxation, On the Complexity of Local Graph Transformations

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A local search approximation algorithm for \(k\)-means clustering
• A factor 2 approximation algorithm for the generalized Steiner network problem
• Constructions for cubic graphs with large girth
• An effective implementation of the Lin-Kernighan traveling salesman heuristic
• Simple PTAS's for families of graphs excluding a minor
• The Power of Dynamic Distance Oracles
• Greedy Algorithms for Steiner Forest
• The Design of Approximation Algorithms
• Designing Network Protocols for Good Equilibria
• A Group-Strategyproof Cost Sharing Mechanism for the Steiner Forest Game
• Saving an epsilon
• Dynamic Steiner Tree Problem
• On Syntactic versus Computational Views of Approximability
• Approximating the Minimum-Degree Steiner Tree to within One of Optimal
• Analysis of a Local Search Heuristic for Facility Location Problems
• Local Search Heuristics for k-Median and Facility Location Problems
• A General Approximation Technique for Constrained Forest Problems
• When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks
• Quasi-Polynomial Local Search for Restricted Max-Min Fair Allocation
• Approximate Integer Decompositions for Undirected Network Design Problems
• Online Steiner Tree with Deletions
• The power of deferral
• An Effective Heuristic Algorithm for the Traveling-Salesman Problem
• Local-Search based Approximation Algorithms for Mobile Facility Location Problems: (Extended Abstract)
• The Power of Recourse for Online MST and TSP