Groß, Martin ;
Gupta, Anupam ;
Kumar, Amit ;
Matuschke, Jannik ;
Schmidt, Daniel R. ;
Schmidt, Melanie ;
Verschae, José
A LocalSearch Algorithm for Steiner Forest
Abstract
In the Steiner Forest problem, we are given a graph and a collection of sourcesink pairs, and the goal is to find a subgraph of minimum total length such that all pairs are connected. The problem is APXHard and can be 2approximated by, e.g., the elegant primaldual algorithm of Agrawal, Klein, and Ravi from 1995.
We give a localsearchbased constantfactor 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 carefullychosen local moves and potential function work in tandem to eliminate bad local minima that arise when using more traditional local moves.
Our analysis first considers the case where the local optimum is a single tree, and shows optimality w.r.t. moves that add a single edge (and drop a set of edges) is enough to bound the locality gap. For the general case, we show how to "project" the optimal solution onto the different trees of the local optimum without incurring too much cost (and this argument uses optimality w.r.t. both kinds of moves), followed by a treebytree argument. We hope both the potential function, and our analysis techniques will be useful to develop and analyze localsearch algorithms in other contexts.
BibTeX  Entry
@InProceedings{gro_et_al:LIPIcs:2018:8313,
author = {Martin Gro{\ss} and Anupam Gupta and Amit Kumar and Jannik Matuschke and Daniel R. Schmidt and Melanie Schmidt and Jos{\'e} Verschae},
title = {{A LocalSearch Algorithm for Steiner Forest}},
booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
pages = {31:131:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770606},
ISSN = {18688969},
year = {2018},
volume = {94},
editor = {Anna R. Karlin},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8313},
URN = {urn:nbn:de:0030drops83134},
doi = {10.4230/LIPIcs.ITCS.2018.31},
annote = {Keywords: Local Search, Steiner Forest, Approximation Algorithms, Network Design}
}
2018
Keywords: 

Local Search, Steiner Forest, Approximation Algorithms, Network Design 
Seminar: 

9th Innovations in Theoretical Computer Science Conference (ITCS 2018)

Issue date: 

2018 
Date of publication: 

2018 