A Local-Search Algorithm for Steiner Forest

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



PDF
Thumbnail PDF

File

LIPIcs.ITCS.2018.31.pdf
  • Filesize: 0.6 MB
  • 17 pages

Document Identifiers

Author Details

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

Cite AsGet BibTex

Martin Groß, Anupam Gupta, Amit Kumar, Jannik Matuschke, Daniel R. Schmidt, Melanie Schmidt, and José Verschae. A Local-Search Algorithm for Steiner Forest. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 31:1-31:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.ITCS.2018.31

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. 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 tree-by-tree argument. We hope both the potential function, and our analysis techniques will be useful to develop and analyze local-search algorithms in other contexts.
Keywords
  • Local Search
  • Steiner Forest
  • Approximation Algorithms
  • Network Design

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Ajit Agrawal, Philip N. Klein, and R. Ravi. When trees collide: An approximation algorithm for the generalized steiner problem on networks. SIAM J. Comput., 24(3):440-456, 1995. URL: http://dx.doi.org/10.1137/S0097539792236237.
  2. Sara Ahmadian, Zachary Friggstad, and Chaitanya Swamy. Local-search Based Approximation Algorithms for Mobile Facility Location Problems. In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '13, pages 1607-1621. SIAM, 2013. URL: http://dl.acm.org/citation.cfm?id=2627817.2627932.
  3. Paola Alimonti. New local search approximation techniques for maximum generalized satisfiability problems. In Maurizio A. Bonuccelli, Pierluigi Crescenzi, and Rossella Petreschi, editors, Algorithms and Complexity, Second Italian Conference, CIAC '94, Rome, Italy, February 23-25, 1994, Proceedings, volume 778 of Lecture Notes in Computer Science, pages 40-53. Springer, 1994. URL: http://dx.doi.org/10.1007/3-540-57811-0_5.
  4. Vijay Arya, Naveen Garg, Rohit Khandekar, Adam Meyerson, Kamesh Munagala, and Vinayaka Pandit. Local search heuristics for k-median and facility location problems. SIAM J. Comput., 33(3):544-562, 2004. URL: http://dx.doi.org/10.1137/S0097539702416402.
  5. Norman Biggs. Constructions for cubic graphs with large girth. The Electronic Journal of Combinatorics, 5(1):A1:1-A1:25, 1998. Google Scholar
  6. Sergio Cabello and David Gajser. Simple ptas’s for families of graphs excluding a minor. Discrete Applied Mathematics, 189:41-48, 2015. URL: http://dx.doi.org/10.1016/j.dam.2015.03.004.
  7. Chandra Chekuri and F. Bruce Shepherd. Approximate integer decompositions for undirected network design problems. SIAM J. Discrete Math., 23(1):163-177, 2008. URL: http://dx.doi.org/10.1137/040617339.
  8. Ho-Lin Chen, Tim Roughgarden, and Gregory Valiant. Designing network protocols for good equilibria. SIAM J. Comput., 39(5):1799-1832, 2010. URL: http://dx.doi.org/10.1137/08072721X.
  9. Vincent Cohen-Addad, Philip N. Klein, and Claire Mathieu. Local search yields approximation schemes for k-means and k-median in euclidean and minor-free metrics. In Proceedings of the 57th Annual Symposium on Foundations of Computer Science, 2016. to appear. Google Scholar
  10. Vincent Cohen-Addad and Claire Mathieu. Effectiveness of local search for geometric optimization. In Lars Arge and János Pach, editors, 31st International Symposium on Computational Geometry, SoCG 2015, June 22-25, 2015, Eindhoven, The Netherlands, volume 34 of LIPIcs, pages 329-343. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2015. URL: http://dx.doi.org/10.4230/LIPIcs.SOCG.2015.329.
  11. Zachary Friggstad, Mohsen Rezapour, and Mohammad R. Salavatipour. Local search yields a PTAS for k-means in doubling metrics. In Proceedings of the 57th Annual Symposium on Foundations of Computer Science, volume abs/1603.08976, 2016. to appear. Google Scholar
  12. Martin Fürer and Balaji Raghavachari. Approximating the minimum-degree steiner tree to within one of optimal. J. Algorithms, 17(3):409-423, 1994. URL: http://dx.doi.org/10.1006/jagm.1994.1042.
  13. Naveen Garg. Saving an epsilon: a 2-approximation for the k-mst problem in graphs. In Harold N. Gabow and Ronald Fagin, editors, Proceedings of the 37th Annual ACM Symposium on Theory of Computing, Baltimore, MD, USA, May 22-24, 2005, pages 396-402. ACM, 2005. URL: http://dx.doi.org/10.1145/1060590.1060650.
  14. Naveen Garg, 2016. Personal Communication. Google Scholar
  15. Michel X. Goemans and David P. Williamson. A general approximation technique for constrained forest problems. SIAM J. Comput., 24(2):296-317, 1995. URL: http://dx.doi.org/10.1137/S0097539793242618.
  16. Albert Gu, Anupam Gupta, and Amit Kumar. The power of deferral: maintaining a constant-competitive steiner tree online. In Dan Boneh, Tim Roughgarden, and Joan Feigenbaum, editors, Symposium on Theory of Computing Conference, STOC'13, Palo Alto, CA, USA, June 1-4, 2013, pages 525-534. ACM, 2013. URL: http://dx.doi.org/10.1145/2488608.2488674.
  17. Anupam Gupta and Amit Kumar. Online steiner tree with deletions. In Chandra Chekuri, editor, Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pages 455-467. SIAM, 2014. URL: http://dx.doi.org/10.1137/1.9781611973402.34.
  18. Anupam Gupta and Amit Kumar. Greedy Algorithms for Steiner Forest. In Ronitt Rubinfeld and Rocco Servedio, editors, Proceedings of the Forty-seventh Annual ACM Symposium on Theory of Computing, STOC '15, pages 871-878. ACM, 2015. Google Scholar
  19. Keld Helsgaun. An effective implementation of the lin-kernighan traveling salesman heuristic. European Journal of Operational Research, 126(1):106-130, 2000. URL: http://dx.doi.org/10.1016/S0377-2217(99)00284-2.
  20. Makoto Imase and Bernard M. Waxman. Dynamic Steiner tree problem. SIAM J. Discrete Math., 4(3):369-384, 1991. Google Scholar
  21. Kamal Jain. A factor 2 approximation algorithm for the generalized steiner network problem. Combinatorica, 21(1):39-60, 2001. URL: http://dx.doi.org/10.1007/s004930170004.
  22. Tapas Kanungo, David M. Mount, Nathan S. Netanyahu, Christine D. Piatko, Ruth Silverman, and Angela Y. Wu. A local search approximation algorithm for k-means clustering. Comput. Geom., 28(2-3):89-112, 2004. URL: http://dx.doi.org/10.1016/j.comgeo.2004.03.003.
  23. Sanjeev Khanna, Rajeev Motwani, Madhu Sudan, and Umesh V. Vazirani. On syntactic versus computational views of approximability. SIAM J. Comput., 28(1):164-191, 1998. URL: http://dx.doi.org/10.1137/S0097539795286612.
  24. Jochen Könemann, Stefano Leonardi, and Guido Schäfer. A Group-Strategyproof Mechanism for Steiner Forests. In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '05, pages 612-619. Society for Industrial and Applied Mathematics, 2005. URL: http://dx.doi.org/10.1.1.126.4369.
  25. Jochen Könemann, Stefano Leonardi, Guido Schäfer, and Stefan H. M. van Zwam. A group-strategyproof cost sharing mechanism for the steiner forest game. SIAM J. Comput., 37(5):1319-1341, 2008. URL: http://dx.doi.org/10.1137/050646408.
  26. Madhukar R. Korupolu, C. Greg Plaxton, and Rajmohan Rajaraman. Analysis of a local search heuristic for facility location problems. J. Algorithms, 37(1):146-188, 2000. URL: http://dx.doi.org/10.1006/jagm.2000.1100.
  27. Jakub Lacki, Jakub Ocwieja, Marcin Pilipczuk, Piotr Sankowski, and Anna Zych. The power of dynamic distance oracles: Efficient dynamic algorithms for the steiner tree. In Rocco A. Servedio and Ronitt Rubinfeld, editors, Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, pages 11-20. ACM, 2015. URL: http://dx.doi.org/10.1145/2746539.2746615.
  28. S. Lin and Brian W. Kernighan. An effective heuristic algorithm for the traveling-salesman problem. Operations Research, 21(2):498-516, 1973. URL: http://dx.doi.org/10.1287/opre.21.2.498.
  29. Hsueh-I Lu and R. Ravi. The Power of Local Optimization: Approximation Algorithms for Maximum-leaf Spanning Tree. In In Proceedings, Thirtieth Annual Allerton Conference on Communication, Control and Computing, pages 533-542, 1996. Google Scholar
  30. Nicole Megow, Martin Skutella, José Verschae, and Andreas Wiese. The power of recourse for online MST and TSP. In Artur Czumaj, Kurt Mehlhorn, Andrew M. Pitts, and Roger Wattenhofer, editors, Automata, Languages, and Programming - 39th International Colloquium, ICALP 2012, Warwick, UK, July 9-13, 2012, Proceedings, Part I, volume 7391 of Lecture Notes in Computer Science, pages 689-700. Springer, 2012. URL: http://dx.doi.org/10.1007/978-3-642-31594-7_58.
  31. Martin Pál, Éva Tardos, and Tom Wexler. Facility location with nonuniform hard capacities. In 42nd Annual Symposium on Foundations of Computer Science, FOCS 2001, 14-17 October 2001, Las Vegas, Nevada, USA, pages 329-338. IEEE Computer Society, 2001. URL: http://dx.doi.org/10.1109/SFCS.2001.959907.
  32. Lukás Polácek and Ola Svensson. Quasi-polynomial local search for restricted max-min fair allocation. ACM Trans. Algorithms, 12(2):13:1-13:13, 2016. URL: http://dx.doi.org/10.1145/2818695.
  33. Roberto Solis-Oba. 2-approximation algorithm for finding a spanning tree with maximum number of leaves. In Gianfranco Bilardi, Giuseppe F. Italiano, Andrea Pietracaprina, and Geppino Pucci, editors, Algorithms - ESA '98, 6th Annual European Symposium, Venice, Italy, August 24-26, 1998, Proceedings, volume 1461 of Lecture Notes in Computer Science, pages 441-452. Springer, 1998. URL: http://dx.doi.org/10.1007/3-540-68530-8_37.
  34. David P Williamson and David B Shmoys. The design of approximation algorithms. Cambridge university press, 2011. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail