A local-search algorithm for Steiner forest. (English) Zbl 1462.68140
Karlin, Anna R. (ed.), 9th innovations in theoretical computer science conference, ITCS 2018, Cambridge, MA, USA, January 11–14, 2018. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 94, Article 31, 17 p. (2018).
Summary: 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 A. Agrawal et al. [SIAM J. Comput. 24, No. 3, 440–456 (1995; Zbl 0831.68071)].
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.
For the entire collection see [Zbl 1379.68009].
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.
For the entire collection see [Zbl 1379.68009].
MSC:
| 68R10 | Graph theory (including graph drawing) in computer science |
| 68W25 | Approximation algorithms |
Citations:
Zbl 0831.68071References:
| [1] | Ajit Agrawal, Philip N. Klein, and R. Ravi. When trees collide: An approximation al gorithm for the generalized steiner problem on networks. {\it SIAM J. Comput.}, 24(3):440-456, 1995. doi:10.1137/S0097539792236237. · Zbl 0831.68071 |
| [2] | Sara Ahmadian, Zachary Friggstad, and Chaitanya Swamy. Local-search Based Approx imation Algorithms for Mobile Facility Location Problems. In {\it Proceedings of the Twenty-} {\it 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. · Zbl 1422.90020 |
| [3] | Paola Alimonti. New local search approximation techniques for maximum generalized sat isfiability problems. In Maurizio A. Bonuccelli, Pierluigi Crescenzi, and Rossella Petreschi, editors, {\it Algorithms and Complexity, Second Italian Conference, CIAC ’94, Rome, Italy,} {\it February 23-25, 1994, Proceedings}, volume 778 of {\it Lecture Notes in Computer Science}, pages 40-53. Springer, 1994. doi: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. {\it SIAM} {\it J. Comput.}, 33(3):544-562, 2004. doi:10.1137/S0097539702416402. · Zbl 1105.68118 |
| [5] | Norman Biggs. Constructions for cubic graphs with large girth. {\it The Electronic Journal of} {\it Combinatorics}, 5(1):A1:1-A1:25, 1998. · Zbl 0911.05036 |
| [6] | Sergio Cabello and David Gajser. Simple ptas’s for families of graphs excluding a minor. {\it Discrete Applied Mathematics}, 189:41-48, 2015. doi:10.1016/j.dam.2015.03.004. · Zbl 1316.05093 |
| [7] | Chandra Chekuri and F. Bruce Shepherd. Approximate integer decompositions for un directed network design problems. {\it SIAM J. Discrete Math.}, 23(1):163-177, 2008. doi: 10.1137/040617339. · Zbl 1185.68849 |
| [8] | Ho-Lin Chen, Tim Roughgarden, and Gregory Valiant. Designing network protocols for good equilibria. {\it SIAM J. Comput.}, 39(5):1799-1832, 2010. doi:10.1137/08072721X. · Zbl 1207.68164 |
| [9] | Vincent Cohen-Addad, Philip N. Klein, and Claire Mathieu. Local search yields approxima tion schemes for k-means and k-median in euclidean and minor-free metrics. In {\it Proceedings} {\it of the 57th Annual Symposium on Foundations of Computer Science}, 2016. to appear. |
| [10] | Vincent Cohen-Addad and Claire Mathieu.Effectiveness of local search for geometric optimization. In Lars Arge and János Pach, editors, {\it 31st International Symposium on} {\it Computational Geometry, SoCG 2015, June 22-25, 2015, Eindhoven, The Netherlands}, volume 34 of {\it LIPIcs}, pages 329-343. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2015. doi:10.4230/LIPIcs.SOCG.2015.329. · Zbl 1378.68167 |
| [11] | Zachary Friggstad, Mohsen Rezapour, and Mohammad R. Salavatipour. Local search yields a PTAS for k-means in doubling metrics. In {\it Proceedings of the 57th Annual Symposium on} {\it Foundations of Computer Science}, volume abs/1603.08976, 2016. to appear. |
| [12] | Martin Fürer and Balaji Raghavachari. Approximating the minimum-degree steiner tree to within one of optimal. {\it J. Algorithms}, 17(3):409-423, 1994. doi:10.1006/jagm.1994.1042. · Zbl 1321.05262 |
| [13] | Naveen Garg.Saving an epsilon: a 2-approximation for the k-mst problem in graphs. In Harold N. Gabow and Ronald Fagin, editors, {\it Proceedings of the 37th Annual ACM} {\it Symposium on Theory of Computing, Baltimore, MD, USA, May 22-24, 2005}, pages 396- 402. ACM, 2005. doi:10.1145/1060590.1060650. · Zbl 1192.05159 |
| [14] | Naveen Garg, 2016. Personal Communication. |
| [15] | Michel X. Goemans and David P. Williamson. A general approximation technique for constrained forest problems.{\it SIAM J. Comput.}, 24(2):296-317, 1995.doi:10.1137/ S0097539793242618. · Zbl 0834.68055 |
| [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, {\it Symposium on Theory of Computing Conference, STOC’13, Palo Alto,} {\it CA, USA, June 1-4, 2013}, pages 525-534. ACM, 2013. doi:10.1145/2488608.2488674. · Zbl 1293.05041 |
| [17] | Anupam Gupta and Amit Kumar. Online steiner tree with deletions. In Chandra Chekuri, editor, {\it Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Al-} {\it gorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014}, pages 455-467. SIAM, 2014. doi:10.1137/1.9781611973402.34. · Zbl 1421.68249 |
| [18] | Anupam Gupta and Amit Kumar. Greedy Algorithms for Steiner Forest. In Ronitt Rubin feld and Rocco Servedio, editors, {\it Proceedings of the Forty-seventh Annual ACM Symposium} {\it on Theory of Computing}, STOC ’15, pages 871-878. ACM, 2015. · Zbl 1321.68504 |
| [19] | Keld Helsgaun. An effective implementation of the lin-kernighan traveling salesman heur istic. {\it European Journal of Operational Research}, 126(1):106-130, 2000. doi:10.1016/ S0377-2217(99)00284-2. · Zbl 0969.90073 |
| [20] | Makoto Imase and Bernard M. Waxman. Dynamic Steiner tree problem. {\it SIAM J. Discrete} {\it Math.}, 4(3):369-384, 1991. · Zbl 0739.05030 |
| [21] | Kamal Jain. A factor 2 approximation algorithm for the generalized steiner network prob lem. {\it Combinatorica}, 21(1):39-60, 2001. doi:10.1007/s004930170004. · Zbl 1107.68533 |
| [22] | Tapas Kanungo, David M. Mount, Nathan S. Netanyahu, Christine D. Piatko, Ruth Silver man, and Angela Y. Wu. A local search approximation algorithm for k-means clustering. {\it Comput. Geom.}, 28(2-3):89-112, 2004. doi:10.1016/j.comgeo.2004.03.003. · Zbl 1077.68109 |
| [23] | Sanjeev Khanna, Rajeev Motwani, Madhu Sudan, and Umesh V. Vazirani. On syntactic versus computational views of approximability. {\it SIAM J. Comput.}, 28(1):164-191, 1998. doi:10.1137/S0097539795286612. · Zbl 0915.68068 |
| [24] | Jochen Könemann, Stefano Leonardi, and Guido Schäfer. A Group-Strategyproof Mechan ism for Steiner Forests. In {\it Proceedings of the Sixteenth Annual ACM-SIAM Symposium on} {\it Discrete Algorithms}, SODA ’05, pages 612-619. Society for Industrial and Applied Math ematics, 2005. doi:10.1.1.126.4369. · Zbl 1297.91017 |
| [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. {\it SIAM J. Comput.}, 37(5):1319-1341, 2008. doi:10.1137/050646408. · Zbl 1225.68272 |
| [26] | Madhukar R. Korupolu, C. Greg Plaxton, and Rajmohan Rajaraman. Analysis of a local search heuristic for facility location problems. {\it J. Algorithms}, 37(1):146-188, 2000. doi: 10.1006/jagm.2000.1100. · Zbl 0962.68044 |
| [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, {\it Proceedings of the Forty-Seventh Annual} · Zbl 1321.68389 |
| [28] | S. Lin and Brian W. Kernighan. An effective heuristic algorithm for the traveling-salesman problem. {\it Operations Research}, 21(2):498-516, 1973. doi:10.1287/opre.21.2.498. · Zbl 0256.90038 |
| [29] | Hsueh-I Lu and R. Ravi. The Power of Local Optimization: Approximation Algorithms for Maximum-leaf Spanning Tree. In {\it In Proceedings, Thirtieth Annual Allerton Conference on} {\it Communication, Control and Computing}, pages 533-542, 1996. |
| [30] | Nicole Megow, Martin Skutella, José Verschae, and Andreas Wiese.The power of re course for online MST and TSP. In Artur Czumaj, Kurt Mehlhorn, Andrew M. Pitts, and Roger Wattenhofer, editors, {\it Automata, Languages, and Programming - 39th Inter-} {\it national Colloquium, ICALP 2012, Warwick, UK, July 9-13, 2012, Proceedings, Part} {\it I}, volume 7391 of {\it Lecture Notes in Computer Science}, pages 689-700. Springer, 2012. doi:10.1007/978-3-642-31594-7_58. · Zbl 1272.68472 |
| [31] | Martin Pál, Éva Tardos, and Tom Wexler. Facility location with nonuniform hard capacit ies. In {\it 42nd Annual Symposium on Foundations of Computer Science, FOCS 2001, 14-17} {\it October 2001, Las Vegas, Nevada, USA}, pages 329-338. IEEE Computer Society, 2001. doi:10.1109/SFCS.2001.959907. |
| [32] | :16 |
| [33] | :15 |
| [34] | :17 length of the remaining edges to {\it g/}4. The solution F is feasible and costs {\it n }− 1. The solution {\it M }costs Ω(log {\it n}). Assume we want to remove an edge {\it e }= {{\it v, w}} ∈ {\it M }and our swap even allows us to add a path to reconnect {\it v }and {\it w }(in the graph where {\it M }{{\it e} |
| [35] | Lukás Polácek and Ola Svensson. Quasi-polynomial local search for restricted max-min fair allocation. {\it ACM Trans. Algorithms}, 12(2):13:1-13:13, 2016. doi:10.1145/2818695. · Zbl 1398.68683 |
| [36] | 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, {\it Algorithms - ESA ’98, 6th Annual European Symposium, Venice,} {\it Italy, August 24-26, 1998, Proceedings}, volume 1461 of {\it Lecture Notes in Computer Science}, pages 441-452. Springer, 1998. doi:10.1007/3-540-68530-8_37. · Zbl 0932.68069 |
| [37] | David P Williamson and David B Shmoys. {\it The design of approximation algorithms}. Cam bridge university press, 2011. · Zbl 1219.90004 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
