A LocalSearch Algorithm for Steiner Forest
Groß, Martin and Gupta, Anupam and Kumar, Amit and Matuschke, Jannik and Schmidt, Daniel R. and Schmidt, Melanie and Verschae, José
(2018)
A LocalSearch Algorithm for Steiner Forest.
Published In:
9th Innovations in Theoretical Computer Science Conference (ITCS 2018), Leibniz International Proceedings in Informatics (LIPIcs). 94 Schloss DagstuhlLeibnizZentrum fuer Informatik 2018, 31:131:17.
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.
Download: 
PDF
 Published Version
Available under License Creative Commons Attribution.
Download (13kB) 

Editorial actions:  View Item (Login required) 
Item Type:  Proceedings article 

Citations:  No citation data. 
Uncontrolled Keywords:  
Subjects: 

Divisions:  Institute of Computer Science > Computer Science Department  Prof. Dr. Juenger 
Additional Information:  doi:10.4230/LIPIcs.ITCS.2018.31 issn:18688969 isbn:9783959770606 
Related URLs: 
ZAIK Number:  UNSPECIFIED 

Depositing User:  Daniel R. Schmidt 
Date Deposited:  26 Feb 2018 12:28 
Last Modified:  13 Mar 2018 09:40 
URI:  http://earchive.informatik.unikoeln.de/id/eprint/918 