Document Open Access Logo

New algorithms for Steiner tree reoptimization

Author Davide Bilò

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2018.19.pdf
  • Filesize: 0.55 MB
  • 14 pages

Document Identifiers

Author Details

Davide Bilò
  • Department of Humanities and Social Sciences, University of Sassari, Via Roma 151, 07100 Sassari (SS), Italy

Cite As Get BibTex

Davide Bilò. New algorithms for Steiner tree reoptimization. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 19:1-19:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.ICALP.2018.19

Abstract

Reoptimization is a setting in which we are given an (near) optimal solution of a problem instance and a local modification that slightly changes the instance. The main goal is that of finding an (near) optimal solution of the modified instance.
We investigate one of the most studied scenarios in reoptimization known as Steiner tree reoptimization. Steiner tree reoptimization is a collection of strongly NP-hard optimization problems that are defined on top of the classical Steiner tree problem and for which several constant-factor approximation algorithms have been designed in the last decade. In this paper we improve upon all these results by developing a novel technique that allows us to design polynomial-time approximation schemes. Remarkably, prior to this paper, no approximation algorithm better than recomputing a solution from scratch was known for the elusive scenario in which the cost of a single edge decreases. Our results are best possible since none of the problems addressed in this paper admits a fully polynomial-time approximation scheme, unless P=NP.

Subject Classification

ACM Subject Classification
  • Theory of computation → Approximation algorithms analysis
Keywords
  • Steiner tree problem
  • reoptimization
  • approximation algorithms

Metrics

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

Related Versions

References

  1. Claudia Archetti, Luca Bertazzi, and Maria Grazia Speranza. Reoptimizing the traveling salesman problem. Networks, 42(3):154-159, 2003. URL: http://dx.doi.org/10.1002/net.10091.
  2. Claudia Archetti, Luca Bertazzi, and Maria Grazia Speranza. Reoptimizing the 0-1 knapsack problem. Discrete Applied Mathematics, 158(17):1879-1887, 2010. URL: http://dx.doi.org/10.1016/j.dam.2010.08.003.
  3. Claudia Archetti, Gianfranco Guastaroba, and Maria Grazia Speranza. Reoptimizing the rural postman problem. Computers & OR, 40(5):1306-1313, 2013. URL: http://dx.doi.org/10.1016/j.cor.2012.12.010.
  4. Giorgio Ausiello, Vincenzo Bonifaci, and Bruno Escoffier. Complexity and Approximation in Reoptimization, pages 101-129. Imperial College Press, 2012. Google Scholar
  5. Giorgio Ausiello, Bruno Escoffier, Jérôme Monnot, and Vangelis Th. Paschos. Reoptimization of minimum and maximum traveling salesman’s tours. J. Discrete Algorithms, 7(4):453-463, 2009. URL: http://dx.doi.org/10.1016/j.jda.2008.12.001.
  6. Michael A. Bender, Martin Farach-Colton, Sándor P. Fekete, Jeremy T. Fineman, and Seth Gilbert. Reallocation problems in scheduling. Algorithmica, 73(2):389-409, 2015. URL: http://dx.doi.org/10.1007/s00453-014-9930-4.
  7. Tobias Berg and Harald Hempel. Reoptimization of traveling salesperson problems: Changing single edge-weights. In Adrian-Horia Dediu, Armand-Mihai Ionescu, and Carlos Martín-Vide, editors, Language and Automata Theory and Applications, Third International Conference, LATA 2009, Tarragona, Spain, April 2-8, 2009. Proceedings, volume 5457 of Lecture Notes in Computer Science, pages 141-151. Springer, 2009. URL: http://dx.doi.org/10.1007/978-3-642-00982-2_12.
  8. Davide Bilò, Hans-Joachim Böckenhauer, Juraj Hromkovic, Richard Královic, Tobias Mömke, Peter Widmayer, and Anna Zych. Reoptimization of Steiner trees. In Joachim Gudmundsson, editor, Algorithm Theory - SWAT 2008, 11th Scandinavian Workshop on Algorithm Theory, Gothenburg, Sweden, July 2-4, 2008, Proceedings, volume 5124 of Lecture Notes in Computer Science, pages 258-269. Springer, 2008. URL: http://dx.doi.org/10.1007/978-3-540-69903-3_24.
  9. Davide Bilò, Hans-Joachim Böckenhauer, Dennis Komm, Richard Královic, Tobias Mömke, Sebastian Seibert, and Anna Zych. Reoptimization of the shortest common superstring problem. Algorithmica, 61(2):227-251, 2011. URL: http://dx.doi.org/10.1007/s00453-010-9419-8.
  10. Davide Bilò, Peter Widmayer, and Anna Zych. Reoptimization of weighted graph and covering problems. In Evripidis Bampis and Martin Skutella, editors, Approximation and Online Algorithms, 6th International Workshop, WAOA 2008, Karlsruhe, Germany, September 18-19, 2008. Revised Papers, volume 5426 of Lecture Notes in Computer Science, pages 201-213. Springer, 2008. URL: http://dx.doi.org/10.1007/978-3-540-93980-1_16.
  11. Davide Bilò and Anna Zych. New advances in reoptimizing the minimum Steiner tree problem. In Branislav Rovan, Vladimiro Sassone, and Peter Widmayer, editors, Mathematical Foundations of Computer Science 2012 - 37th International Symposium, MFCS 2012, Bratislava, Slovakia, August 27-31, 2012. Proceedings, volume 7464 of Lecture Notes in Computer Science, pages 184-197. Springer, 2012. URL: http://dx.doi.org/10.1007/978-3-642-32589-2_19.
  12. Hans-Joachim Böckenhauer, Luca Forlizzi, Juraj Hromkovic, Joachim Kneis, Joachim Kupke, Guido Proietti, and Peter Widmayer. On the approximability of TSP on local modifications of optimally solved instances. Algorithmic Operations Research, 2(2):83-93, 2007. URL: http://journals.hil.unb.ca/index.php/AOR/article/view/2803.
  13. Hans-Joachim Böckenhauer, Karin Freiermuth, Juraj Hromkovic, Tobias Mömke, Andreas Sprock, and Björn Steffen. Steiner tree reoptimization in graphs with sharpened triangle inequality. J. Discrete Algorithms, 11:73-86, 2012. URL: http://dx.doi.org/10.1016/j.jda.2011.03.014.
  14. Hans-Joachim Böckenhauer, Juraj Hromkovic, Richard Královic, Tobias Mömke, and Peter Rossmanith. Reoptimization of Steiner trees: Changing the terminal set. Theor. Comput. Sci., 410(36):3428-3435, 2009. URL: http://dx.doi.org/10.1016/j.tcs.2008.04.039.
  15. Hans-Joachim Böckenhauer, Juraj Hromkovic, Tobias Mömke, and Peter Widmayer. On the hardness of reoptimization. In Viliam Geffert, Juhani Karhumäki, Alberto Bertoni, Bart Preneel, Pavol Návrat, and Mária Bieliková, editors, SOFSEM 2008: Theory and Practice of Computer Science, 34th Conference on Current Trends in Theory and Practice of Computer Science, Nový Smokovec, Slovakia, January 19-25, 2008, Proceedings, volume 4910 of Lecture Notes in Computer Science, pages 50-65. Springer, 2008. URL: http://dx.doi.org/10.1007/978-3-540-77566-9_5.
  16. Hans-Joachim Böckenhauer, Juraj Hromkovic, and Andreas Sprock. Knowing all optimal solutions does not help for TSP reoptimization. In Jozef Kelemen and Alica Kelemenová, editors, Computation, Cooperation, and Life - Essays Dedicated to Gheorghe Paun on the Occasion of His 60th Birthday, volume 6610 of Lecture Notes in Computer Science, pages 7-15. Springer, 2011. URL: http://dx.doi.org/10.1007/978-3-642-20000-7_2.
  17. Hans-Joachim Böckenhauer, Juraj Hromkovic, and Andreas Sprock. On the hardness of reoptimization with multiple given solutions. Fundam. Inform., 110(1-4):59-76, 2011. URL: http://dx.doi.org/10.3233/FI-2011-528.
  18. Hans-Joachim Böckenhauer, Joachim Kneis, and Joachim Kupke. Approximation hardness of deadline-TSP reoptimization. Theor. Comput. Sci., 410(21-23):2241-2249, 2009. URL: http://dx.doi.org/10.1016/j.tcs.2009.02.016.
  19. Hans-Joachim Böckenhauer and Dennis Komm. Reoptimization of the metric deadline TSP. J. Discrete Algorithms, 8(1):87-100, 2010. URL: http://dx.doi.org/10.1016/j.jda.2009.04.001.
  20. Al Borchers and Ding-Zhu Du. The k-Steiner ratio in graphs. SIAM J. Comput., 26(3):857-869, 1997. URL: http://dx.doi.org/10.1137/S0097539795281086.
  21. Nicolas Boria and Federico Della Croce. Reoptimization in machine scheduling. Theor. Comput. Sci., 540:13-26, 2014. URL: http://dx.doi.org/10.1016/j.tcs.2014.04.004.
  22. Nicolas Boria, Jérôme Monnot, and Vangelis Th. Paschos. Reoptimization of maximum weight induced hereditary subgraph problems. Theor. Comput. Sci., 514:61-74, 2013. URL: http://dx.doi.org/10.1016/j.tcs.2012.10.037.
  23. Nicolas Boria, Jérôme Monnot, and Vangelis Th. Paschos. Reoptimization under vertex insertion: Max p_k-free subgraph and max planar subgraph. Discrete Math., Alg. and Appl., 5(2), 2013. URL: http://dx.doi.org/10.1142/S1793830913600045.
  24. Nicolas Boria and Vangelis Th. Paschos. Fast reoptimization for the minimum spanning tree problem. J. Discrete Algorithms, 8(3):296-310, 2010. URL: http://dx.doi.org/10.1016/j.jda.2009.07.002.
  25. Nicolas Boria and Vangelis Th. Paschos. A survey on combinatorial optimization in dynamic environments. RAIRO - Operations Research, 45(3):241-294, 2011. URL: http://dx.doi.org/10.1051/ro/2011114.
  26. Jaroslaw Byrka, Fabrizio Grandoni, Thomas Rothvoß, and Laura Sanità. Steiner tree approximation via iterative randomized rounding. J. ACM, 60(1):6:1-6:33, 2013. URL: http://dx.doi.org/10.1145/2432622.2432628.
  27. Wenkai Dai. Reoptimization of minimum latency problem. In Yixin Cao and Jianer Chen, editors, Computing and Combinatorics - 23rd International Conference, COCOON 2017, Hong Kong, China, August 3-5, 2017, Proceedings, volume 10392 of Lecture Notes in Computer Science, pages 162-174. Springer, 2017. URL: http://dx.doi.org/10.1007/978-3-319-62389-4_14.
  28. S. E. Dreyfus and R. A. Wagner. The steiner problem in graphs. Networks, 1(3):195-207, 1971. URL: http://dx.doi.org/10.1002/net.3230010302.
  29. Bruno Escoffier, Martin Milanic, and Vangelis Th. Paschos. Simple and fast reoptimizations for the Steiner tree problem. Algorithmic Operations Research, 4(2):86-94, 2009. URL: http://journals.hil.unb.ca/index.php/AOR/article/view/5653.
  30. Keshav Goyal and Tobias Mömke. Robust reoptimization of Steiner trees. In Prahladh Harsha and G. Ramalingam, editors, 35th IARCS Annual Conference on Foundation of Software Technology and Theoretical Computer Science, FSTTCS 2015, December 16-18, 2015, Bangalore, India, volume 45 of LIPIcs, pages 10-24. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2015. URL: http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2015.10.
  31. Stefan Hougardy, Jannik Silvanus, and Jens Vygen. Dijkstra meets Steiner: a fast exact goal-oriented Steiner tree algorithm. Math. Program. Comput., 9(2):135-202, 2017. URL: http://dx.doi.org/10.1007/s12532-016-0110-1.
  32. Jérôme Monnot. A note on the traveling salesman reoptimization problem under vertex insertion. Inf. Process. Lett., 115(3):435-438, 2015. URL: http://dx.doi.org/10.1016/j.ipl.2014.11.003.
  33. Markus W. Schäffter. Scheduling with forbidden sets. Discrete Applied Mathematics, 72(1-2):155-166, 1997. URL: http://dx.doi.org/10.1016/S0166-218X(96)00042-X.
  34. Anna Zych. Reoptimization of NP-hard problems. PhD thesis, Diss., Eidgenössische Technische Hochschule ETH Zürich, Nr. 20257, 2012. Google Scholar
  35. Anna Zych and Davide Bilò. New reoptimization techniques applied to Steiner tree problem. Electronic Notes in Discrete Mathematics, 37:387-392, 2011. URL: http://dx.doi.org/10.1016/j.endm.2011.05.066.
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
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact