TSP With Locational Uncertainty: The Adversarial Model

Authors Gui Citovsky, Tyler Mayer, Joseph S. B. Mitchell



PDF
Thumbnail PDF

File

LIPIcs.SoCG.2017.32.pdf
  • Filesize: 0.63 MB
  • 16 pages

Document Identifiers

Author Details

Gui Citovsky
Tyler Mayer
Joseph S. B. Mitchell

Cite AsGet BibTex

Gui Citovsky, Tyler Mayer, and Joseph S. B. Mitchell. TSP With Locational Uncertainty: The Adversarial Model. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 32:1-32:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.SoCG.2017.32

Abstract

In this paper we study a natural special case of the Traveling Salesman Problem (TSP) with point-locational-uncertainty which we will call the adversarial TSP problem (ATSP). Given a metric space (X, d) and a set of subsets R = {R_1, R_2, ... , R_n} : R_i subseteq X, the goal is to devise an ordering of the regions, sigma_R, that the tour will visit such that when a single point is chosen from each region, the induced tour over those points in the ordering prescribed by sigma_R is as short as possible. Unlike the classical locational-uncertainty-TSP problem, which focuses on minimizing the expected length of such a tour when the point within each region is chosen according to some probability distribution, here, we focus on the adversarial model in which once the choice of sigma_R is announced, an adversary selects a point from each region in order to make the resulting tour as long as possible. In other words, we consider an offline problem in which the goal is to determine an ordering of the regions R that is optimal with respect to the ``worst'' point possible within each region being chosen by an adversary, who knows the chosen ordering. We give a 3-approximation when R is a set of arbitrary regions/sets of points in a metric space. We show how geometry leads to improved constant factor approximations when regions are parallel line segments of the same lengths, and a polynomial-time approximation scheme (PTAS) for the important special case in which R is a set of disjoint unit disks in the plane.
Keywords
  • traveling salesperson problem
  • TSP with neighborhoods
  • approximation algorithms
  • uncertainty

Metrics

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

References

  1. Esther M. Arkin and Refael Hassin. Approximation algorithms for the geometric covering salesman problem. Discrete Applied Mathematics, 55(3):197-218, 1994. Google Scholar
  2. Dimitris J. Bertsimas, Patrick Jaillet, and Amedeo R. Odoni. A priori optimization. Operations Research, 38(6):1019-1033, 1990. Google Scholar
  3. Gui Citovsky, Tyler Mayer, and Joseph S. B. Mitchell. TSP With Locational Uncertainty: The Adversarial Model, March 2017. arXiv:1705.06180 [cs.CG]. URL: https://arxiv.org/abs/1705.06180.
  4. Reza Dorrigiv, Robert Fraser, Meng He, Shahin Kamali, Akitoshi Kawamura, Alejandro López-Ortiz, and Diego Seco. On minimum-and maximum-weight minimum spanning trees with neighborhoods. Theory of Computing Systems, 56(1):220-250, 2015. Google Scholar
  5. Adrian Dumitrescu and Joseph S. B. Mitchell. Approximation algorithms for TSP with neighborhoods in the plane. Journal of Algorithms, 48:135-159, 2003. Special issue devoted to 12th ACM-SIAM Symposium on Discrete Algorithms, Washington, DC, January, 2001. Google Scholar
  6. Robert Fraser. Algorithms for geometric covering and piercing problems. PhD thesis, University of Waterloo, 2012. Google Scholar
  7. Patrick Jaillet. A priori solution of a traveling salesman problem in which a random subset of the customers are visited. Operations Research, 36(6):929-936, 1988. Google Scholar
  8. Lujun Jia, Guolong Lin, Guevara Noubir, Rajmohan Rajaraman, and Ravi Sundaram. Universal approximations for TSP, Steiner tree, and set cover. In Proc. 37th ACM Symposium on Theory of Computing, pages 386-395. ACM, 2005. Google Scholar
  9. Pegah Kamousi and Subhash Suri. Euclidean traveling salesman tours through stochastic neighborhoods. In International Symposium on Algorithms and Computation, pages 644-654. Springer, 2013. Google Scholar
  10. Chih-Hung Liu and Sandro Montanari. Minimizing the diameter of a spanning tree for imprecise points. In International Symposium on Algorithms and Computation, pages 381-392. Springer, 2015. Google Scholar
  11. Maarten Löffler and Marc van Kreveld. Largest and smallest convex hulls for imprecise points. Algorithmica, 56(2):235-269, 2010. Google Scholar
  12. Joseph S. B. Mitchell. Guillotine subdivisions approximate polygonal subdivisions: A simple polynomial-time approximation scheme for geometric TSP, k-MST, and related problems. SIAM Journal on Computing, 28(4):1298-1309, 1999. Google Scholar
  13. Joseph S. B. Mitchell. Shortest paths and networks. In Jacob E. Goodman and Joseph O'Rourke, editors, Handbook of Discrete and Computational Geometry (2nd Edition), chapter 27, pages 607-641. Chapman &Hall/CRC, Boca Raton, FL, 2004. Google Scholar
  14. Joseph S. B. Mitchell. A PTAS for TSP with neighborhoods among fat regions in the plane. In Proc. 18th ACM-SIAM Symposium on Discrete algorithms, pages 11-18. Society for Industrial and Applied Mathematics, 2007. URL: http://www.ams.sunysb.edu/~jsbm/papers/tspn-soda07-rev.pdf.
  15. Sandro Montanari. Computing routes and trees under uncertainty. PhD thesis, Dissertation, ETH-Zürich, 2015, No. 23042, 2015. Google Scholar
  16. Yang Yang, Mingen Lin, Jinhui Xu, and Yulai Xie. Minimum spanning tree with neighborhoods. In International Conference on Algorithmic Applications in Management, pages 306-316. Springer, 2007. 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