Robust Reoptimization of Steiner Trees

Authors Keshav Goyal, Tobias Mömke



PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2015.10.pdf
  • Filesize: 0.56 MB
  • 15 pages

Document Identifiers

Author Details

Keshav Goyal
Tobias Mömke

Cite AsGet BibTex

Keshav Goyal and Tobias Mömke. Robust Reoptimization of Steiner Trees. In 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 45, pp. 10-24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
https://doi.org/10.4230/LIPIcs.FSTTCS.2015.10

Abstract

In reoptimization problems, one is given an optimal solution to a problem instance and a local modification of the instance. The goal is to obtain a solution for the modified instance. The additional information about the instance provided by the given solution plays a central role: we aim to use that information in order to obtain better solutions than we are able to compute from scratch. In this paper, we consider Steiner tree reoptimization and address the optimality requirement of the provided solution. Instead of assuming that we are provided an optimal solution, we relax the assumption to the more realistic scenario where we are given an approximate solution with an upper bound on its performance guarantee. We show that for Steiner tree reoptimization there is a clear separation between local modifications where optimality is crucial for obtaining improved approximations and those instances where approximate solutions are acceptable starting points. For some of the local modifications that have been considered in previous research, we show that for every fixed epsilon > 0, approximating the reoptimization problem with respect to a given (1+epsilon)-approximation is as hard as approximating the Steiner tree problem itself (whereas with a given optimal solution to the original problem it is known that one can obtain considerably improved results). Furthermore, we provide a new algorithmic technique that, with some further insights, allows us to obtain improved performance guarantees for Steiner tree reoptimization with respect to all remaining local modifications that have been considered in the literature: a required node of degree more than one becomes a Steiner node; a Steiner node becomes a required node; the cost of one edge is increased.
Keywords
  • reoptimization
  • approximation algorithms
  • Steiner tree problem
  • robustness

Metrics

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

References

  1. Claudia Archetti, Luca Bertazzi, and Maria Grazia Speranza. Reoptimizing the traveling salesman problem. Networks, 42(3):154-159, 2003. Google Scholar
  2. Claudia Archetti, Luca Bertazzi, and Maria Grazia Speranza. Reoptimizing the 0-1 knapsack problem. Discrete Applied Mathematics, 158(17):1879-1887, 2010. Google Scholar
  3. Claudia Archetti, Gianfranco Guastaroba, and Maria Grazia Speranza. Reoptimizing the rural postman problem. Computers & OR, 40(5):1306-1313, 2013. Google Scholar
  4. Giorgio Ausiello, Vincenzo Bonifaci, and Bruno Escoffier. Complexity and approximation in reoptimization. Imperial College Press/World Scientific, 2011. Google Scholar
  5. Giorgio Ausiello, Bruno Escoffier, Jérôme Monnot, and Vangelis Th. Paschos. Reoptimization of minimum and maximum traveling salesman’s tours. Journal of Discrete Algorithms, 7(4):453-463, 2009. Google Scholar
  6. Michael A. Bender, Martin Farach-Colton, Sándor P. Fekete, Jeremy T. Fineman, and Seth Gilbert. Reallocation problems in scheduling. In Proc. of the 25th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2013), pages 271-279. ACM, 2013. Google Scholar
  7. Tobias Berg and Harald Hempel. Reoptimization of traveling salesperson problems: Changing single edge-weights. In Proc. of the Third International Conference on Language and Automata Theory and Applications (LATA 2009), volume 5457 of LNCS, pages 141-151. Springer, 2009. Google Scholar
  8. Marshall W. Bern and Paul E. Plassmann. The Steiner problem with edge lengths 1 and 2. Information Processing Letters, 32(4):171-176, 1989. Google Scholar
  9. Davide Bilò, Hans-Joachim Böckenhauer, Juraj Hromkovič, Richard Královič, Tobias Mömke, Peter Widmayer, and Anna Zych. Reoptimization of Steiner trees. In Proc. of the 11th Scandinavian Workshop on Algorithm Theory (SWAT 2008), volume 5124 of LNCS, pages 258-269, 2008. Google Scholar
  10. 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. Google Scholar
  11. Davide Bilò, Peter Widmayer, and Anna Zych. Reoptimization of weighted graph and covering problems. In Proc. of the 6th International Workshop on Approximation and Online Algorithms (WAOA 2008), volume 5426 of Lecture Notes in Computer Science, pages 201-213. Springer, 2008. Google Scholar
  12. Davide Bilò and Anna Zych. New reoptimization techniques employed to Steiner tree problem. In Proceedings of the 6th Latin-American Algorithms, Graphs and Optimization Symposium (LAGOS 11), 2011. Google Scholar
  13. Davide Bilò and Anna Zych. New advances in reoptimizing the minimum Steiner tree problem. In Mathematical Foundations of Computer Science 2012, pages 184-197. Springer, 2012. Google Scholar
  14. Hans-Joachim Böckenhauer, Luca Forlizzi, Juraj Hromkovič, 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. Google Scholar
  15. Hans-Joachim Böckenhauer, Karin Freiermuth, Juraj Hromkovič, Tobias Mömke, Andreas Sprock, and Björn Steffen. The Steiner tree reoptimization problem in graphs with sharpened triangle inequality. Journal of Discrete Algorithms, 11:73-86, 2012. Google Scholar
  16. Hans-Joachim Böckenhauer, Juraj Hromkovič, Richard Královič, Tobias Mömke, and Peter Rossmanith. Reoptimization of Steiner trees: Changing the terminal set. Theoretical Computer Science, 410(36):3428-3435, 2009. Google Scholar
  17. Hans-Joachim Böckenhauer, Juraj Hromkovič, Tobias Mömke, and Peter Widmayer. On the hardness of reoptimization. In Proc. of the 34th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2008), volume 4910 of LNCS, pages 50-65, 2008. Google Scholar
  18. Hans-Joachim Böckenhauer and Dennis Komm. Reoptimization of the metric deadline TSP. Journal of Discrete Algorithms, 8(1):87-100, 2010. Google Scholar
  19. Al Borchers and Ding-Zhu Du. The k-Steiner ratio in graphs. SIAM Journal on Computing, 26(3):857-869, 1997. Google Scholar
  20. Nicolas Boria and Federico Della Croce. Reoptimization in machine scheduling. Theoretical Computer Science, 540:13-26, 2014. Google Scholar
  21. Nicolas Boria, Jérôme Monnot, and Vangelis Th Paschos. Reoptimization of maximum weight induced hereditary subgraph problems. Theoretical Computer Science, 514:61-74, 2013. Google Scholar
  22. Nicolas Boria and Vangelis T Paschos. A survey on combinatorial optimization in dynamic environments. RAIRO-Operations Research, 45(03):241-294, 2011. Google Scholar
  23. Nicolas Boria and Vangelis Th Paschos. Fast reoptimization for the minimum spanning tree problem. Journal of Discrete Algorithms, 8(3):296-310, 2010. Google Scholar
  24. Jaroslaw Byrka, Fabrizio Grandoni, Thomas Rothvoß, and Laura Sanità. Steiner tree approximation via iterative randomized rounding. Journal of the ACM, 60(1):6, 2013. Google Scholar
  25. S. E. Dreyfus and R. A. Wagner. The Steiner problem in graphs. Networks, 1:195-207, 1971/72. Google Scholar
  26. Bruno Escoffier, Martin Milanič, and Vangelis Th. Paschos. Simple and fast reoptimizations for the Steiner tree problem. Algorithmic Operations Research, 4(2):86-94, 2009. Google Scholar
  27. Stefan Hougardy, Jannik Silvanus, and Jens Vygen. Dijkstra meets Steiner: a fast exact goal-oriented Steiner tree algorithm. arXiv preprint arXiv:1406.0492, 2014. Google Scholar
  28. Jérôme Monnot. A note on the traveling salesman reoptimization problem under vertex insertion. Inf. Process. Lett., 115(3):435-438, 2015. Google Scholar
  29. Markus W Schäffter. Scheduling with forbidden sets. Discrete Applied Mathematics, 72(1):155-166, 1997. Google Scholar
  30. Hiromitsu Takahashi and Akira Matsuyama. An approximate solution for the Steiner problem in graphs. Mathematica Japonica, 24(6):573-577, 1979/80. Google Scholar
  31. Anna Zych. Reoptimization of NP-hard problems. PhD thesis, Diss., Eidgenössische Technische Hochschule ETH Zürich, Nr. 20257, 2012, 2012. 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