Document Open Access Logo

Robust Algorithms for TSP and Steiner Tree

Authors Arun Ganesh, Bruce M. Maggs, Debmalya Panigrahi

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2020.54.pdf
  • Filesize: 0.56 MB
  • 18 pages

Document Identifiers

Author Details

Arun Ganesh
  • Department of Electrical Engineering and Computer Sciences, University of California at Berkeley, CA, USA
Bruce M. Maggs
  • Department of Computer Science, Duke University, Durham, NC, USA
  • Emerald Innovations, Cambridge, MA, USA
Debmalya Panigrahi
  • Department of Computer Science, Duke University, Durham, NC, USA

Funding

  • Ganesh, Arun: Supported in part by NSF Award CCF-1535989.
  • Maggs, Bruce M.: Supported in part by NSF Award CCF-1535972.
  • Panigrahi, Debmalya: Supported in part by NSF grants CCF-1535972, CCF-1955703, an NSF CAREER Award CCF-1750140, and the Indo-US Virtual Networked Joint Center on Algorithms under Uncertainty.

Cite AsGet BibTex

Arun Ganesh, Bruce M. Maggs, and Debmalya Panigrahi. Robust Algorithms for TSP and Steiner Tree. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 54:1-54:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ICALP.2020.54

Abstract

Robust optimization is a widely studied area in operations research, where the algorithm takes as input a range of values and outputs a single solution that performs well for the entire range. Specifically, a robust algorithm aims to minimize regret, defined as the maximum difference between the solution’s cost and that of an optimal solution in hindsight once the input has been realized. For graph problems in P, such as shortest path and minimum spanning tree, robust polynomial-time algorithms that obtain a constant approximation on regret are known. In this paper, we study robust algorithms for minimizing regret in NP-hard graph optimization problems, and give constant approximations on regret for the classical traveling salesman and Steiner tree problems.

Subject Classification

ACM Subject Classification
  • Theory of computation → Routing and network design problems
Keywords
  • Robust optimization
  • Steiner tree
  • traveling salesman problem

Metrics

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

Related Versions

References

  1. H. Aissi, C. Bazgan, and D. Vanderpooten. Complexity of the min–max (regret) versions of min cut problems. Discrete Optimization, 5(1):66-73, 2008. URL: https://doi.org/10.1016/j.disopt.2007.11.008.
  2. Hassene Aissi, Cristina Bazgan, and Daniel Vanderpooten. Min–max and min–max regret versions of combinatorial optimization problems: A survey. European Journal of Operational Research, 197(2):427-438, 2009. URL: https://doi.org/10.1016/j.ejor.2008.09.012.
  3. I. Averbakh and Oded Berman. Minimax regret p-center location on a network with demand uncertainty. Location Science, 5(4):247-254, 1997. URL: https://doi.org/10.1016/S0966-8349(98)00033-3.
  4. Igor Averbakh. On the complexity of a class of combinatorial optimization problems with uncertainty. Mathematical Programming, 90(2):263-272, April 2001. URL: https://doi.org/10.1007/PL00011424.
  5. Igor Averbakh. The minmax relative regret median problem on networks. INFORMS Journal on Computing, 17(4):451-461, 2005. URL: https://doi.org/10.1287/ijoc.1040.0080.
  6. Igor Averbakh and Oded Berman. Minmax regret median location on a network under uncertainty. INFORMS Journal on Computing, 12(2):104-110, 2000. URL: https://doi.org/10.1287/ijoc.12.2.104.11897.
  7. Dimitris Bertsimas and Melvyn Sim. Robust discrete optimization and network flows. Mathematical Programming, 98(1):49-71, September 2003. URL: https://doi.org/10.1007/s10107-003-0396-4.
  8. Moses Charikar, Chandra Chekuri, and Martin Pál. Sampling bounds for stochastic optimization. In Proceedings of the 8th International Workshop on Approximation, Randomization and Combinatorial Optimization Problems, and Proceedings of the 9th International Conference on Randamization and Computation: Algorithms and Techniques, APPROX'05/RANDOM'05, pages 257-269, Berlin, Heidelberg, 2005. Springer-Verlag. URL: https://doi.org/10.1007/11538462_22.
  9. André Chassein and Marc Goerigk. On the recoverable robust traveling salesman problem. Optimization Letters, 10, September 2015. URL: https://doi.org/10.1007/s11590-015-0949-5.
  10. Chandra Chekuri. Routing and network design with robustness to changing or uncertain traffic demands. SIGACT News, 38(3):106-129, 2007. URL: https://doi.org/10.1145/1324215.1324236.
  11. Miroslav Chlebík and Janka Chlebíková. Approximation hardness of the Steiner tree problem on graphs. In Martti Penttonen and Erik Meineche Schmidt, editors, Algorithm Theory - SWAT 2002, pages 170-179, Berlin, Heidelberg, 2002. Springer Berlin Heidelberg. URL: https://doi.org/10.1007/3-540-45471-3_18.
  12. Eduardo Conde. On a constant factor approximation for minmax regret problems using a symmetry point scenario. European Journal of Operational Research, 219(2):452-457, 2012. URL: https://doi.org/10.1016/j.ejor.2012.01.005.
  13. Kedar Dhamdhere, Vineet Goyal, R. Ravi, and Mohit Singh. How to pay, come what may: Approximation algorithms for demand-robust covering problems. In 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 23-25 October 2005, Pittsburgh, PA, USA, Proceedings, pages 367-378, 2005. URL: https://doi.org/10.1109/SFCS.2005.42.
  14. Uriel Feige, Kamal Jain, Mohammad Mahdian, and Vahab S. Mirrokni. Robust combinatorial optimization with exponential scenarios. In Integer Programming and Combinatorial Optimization, 12th International IPCO Conference, Ithaca, NY, USA, June 25-27, 2007, Proceedings, pages 439-453, 2007. URL: https://doi.org/10.1007/978-3-540-72792-7_33.
  15. Navin Goyal, Neil Olver, and F. Bruce Shepherd. The VPN conjecture is true. J. ACM, 60(3):17:1-17:17, 2013. URL: https://doi.org/10.1145/2487241.2487243.
  16. 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, January 11-14, 2018, Cambridge, MA, USA, pages 31:1-31:17, 2018. URL: https://doi.org/10.4230/LIPIcs.ITCS.2018.31.
  17. Anupam Gupta, Jon M. Kleinberg, Amit Kumar, Rajeev Rastogi, and Bülent Yener. Provisioning a virtual private network: a network design problem for multicommodity flow. In Proceedings on 33rd Annual ACM Symposium on Theory of Computing, July 6-8, 2001, Heraklion, Crete, Greece, pages 389-398, 2001. URL: https://doi.org/10.1145/380752.380830.
  18. Anupam Gupta, Viswanath Nagarajan, and R. Ravi. Thresholded covering algorithms for robust and max-min optimization. Math. Program., 146(1-2):583-615, 2014. URL: https://doi.org/10.1007/s10107-013-0705-5.
  19. Anupam Gupta, Viswanath Nagarajan, and R. Ravi. Robust and maxmin optimization under matroid and knapsack uncertainty sets. ACM Trans. Algorithms, 12(1):10:1-10:21, 2016. URL: https://doi.org/10.1145/2746226.
  20. Anupam Gupta, Martin Pál, R. Ravi, and Amitabh Sinha. Boosted sampling: Approximation algorithms for stochastic optimization. In Proceedings of the Thirty-sixth Annual ACM Symposium on Theory of Computing, STOC '04, pages 417-426, New York, NY, USA, 2004. ACM. URL: https://doi.org/10.1145/1007352.1007419.
  21. Masahiro Inuiguchi and Masatoshi Sakawa. Minimax regret solution to linear programming problems with an interval objective function. European Journal of Operational Research, 86(3):526-536, 1995. URL: https://doi.org/10.1016/0377-2217(94)00092-Q.
  22. Marek Karpinski, Michael Lampis, and Richard Schmied. New inapproximability bounds for TSP. In Leizhen Cai, Siu-Wing Cheng, and Tak-Wah Lam, editors, Algorithms and Computation, pages 568-578, Berlin, Heidelberg, 2013. Springer Berlin Heidelberg. URL: https://doi.org/10.1016/j.jcss.2015.06.003.
  23. Adam Kasperski and PawełZieliński. An approximation algorithm for interval data minmax regret combinatorial optimization problems. Inf. Process. Lett., 97(5):177-180, March 2006. URL: https://doi.org/10.1016/j.ipl.2005.11.001.
  24. Adam Kasperski and Pawel Zieliński. On the existence of an FPTAS for minmax regret combinatorial optimization problems with interval data. Oper. Res. Lett., 35:525-532, 2007. URL: https://doi.org/10.1016/j.orl.2006.09.007.
  25. Rohit Khandekar, Guy Kortsarz, Vahab S. Mirrokni, and Mohammad R. Salavatipour. Two-stage robust network design with exponential scenarios. Algorithmica, 65(2):391-408, 2013. URL: https://doi.org/10.1007/s00453-011-9596-0.
  26. P. Kouvelis and G. Yu. Robust Discrete Optimization and Its Applications. Springer US, 1996. Google Scholar
  27. Panos Kouvelis and Gang Yu. Robust 1-Median Location Problems: Dynamic Aspects and Uncertainty, pages 193-240. Springer US, Boston, MA, 1997. URL: https://doi.org/10.1007/978-1-4757-2620-6_6.
  28. Helmut E. Mausser and Manuel Laguna. A new mixed integer formulation for the maximum regret problem. International Transactions in Operational Research, 5(5):389-403, 1998. URL: https://doi.org/10.1016/S0969-6016(98)00023-9.
  29. David B. Shmoys and Chaitanya Swamy. An approximation scheme for stochastic linear programming and its application to stochastic integer programs. J. ACM, 53(6):978-1012, November 2006. URL: https://doi.org/10.1145/1217856.1217860.
  30. Chaitanya Swamy and David B. Shmoys. Approximation algorithms for 2-stage stochastic optimization problems. SIGACT News, 37(1):33-46, 2006. URL: https://doi.org/10.1145/1122480.1122493.
  31. Chaitanya Swamy and David B. Shmoys. Sampling-based approximation algorithms for multistage stochastic optimization. SIAM J. Comput., 41(4):975-1004, 2012. URL: https://doi.org/10.1137/100789269.
  32. Jens Vygen. New approximation algorithms for the tsp. Google Scholar
  33. H. Yaman, O. E. Karaşan, and M. Ç. Pinar. The robust spanning tree problem with interval data. Operations Research Letters, 29(1):31-40, 2001. URL: https://doi.org/10.1016/S0167-6377(01)00078-5.
  34. P. Zieliński. The computational complexity of the relative robust shortest path problem with interval data. European Journal of Operational Research, 158(3):570-576, 2004. URL: https://doi.org/10.1016/S0377-2217(03)00373-4.
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 Imprint Privacy Contact