Constant-Factor Approximation to Deadline TSP and Related Problems in (Almost) Quasi-Polytime

Authors Zachary Friggstad, Chaitanya Swamy



PDF
Thumbnail PDF

File

LIPIcs.ICALP.2021.67.pdf
  • Filesize: 0.83 MB
  • 21 pages

Document Identifiers

Author Details

Zachary Friggstad
  • Department of Computer Science, University of Alberta, Edmonton, Canada
Chaitanya Swamy
  • Department of Combinatorics and Optimization, University of Waterloo, Canada

Cite AsGet BibTex

Zachary Friggstad and Chaitanya Swamy. Constant-Factor Approximation to Deadline TSP and Related Problems in (Almost) Quasi-Polytime. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 67:1-67:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ICALP.2021.67

Abstract

We investigate a genre of vehicle-routing problems (VRPs), that we call max-reward VRPs, wherein nodes located in a metric space have associated rewards that depend on their visiting times, and we seek a path that earns maximum reward. A prominent problem in this genre is deadline TSP, where nodes have deadlines and we seek a path that visits all nodes by their deadlines and earns maximum reward. Our main result is a constant-factor approximation for deadline TSP running in time O(n^O(log(nΔ))) in metric spaces with integer distances at most Δ. This is the first improvement over the approximation factor of O(log n) due to Bansal et al. [N. Bansal et al., 2004] in over 15 years (but is achieved in super-polynomial time). Our result provides the first concrete indication that log n is unlikely to be a real inapproximability barrier for deadline TSP, and raises the exciting possibility that deadline TSP might admit a polytime constant-factor approximation. At a high level, we obtain our result by carefully guessing an appropriate sequence of O(log (nΔ)) nodes appearing on the optimal path, and finding suitable paths between any two consecutive guessed nodes. We argue that the problem of finding a path between two consecutive guessed nodes can be relaxed to an instance of a special case of deadline TSP called point-to-point (P2P) orienteering. Any approximation algorithm for P2P orienteering can then be utilized in conjunction with either a greedy approach, or an LP-rounding approach, to find a good set of paths overall between every pair of guessed nodes. While concatenating these paths does not immediately yield a feasible solution, we argue that it can be covered by a constant number of feasible solutions. Overall our result therefore provides a novel reduction showing that any α-approximation for P2P orienteering can be leveraged to obtain an O(α)-approximation for deadline TSP in O(n^O(log nΔ)) time. Our results extend to yield the same guarantees (in approximation ratio and running time) for a substantial generalization of deadline TSP, where the reward obtained by a client is given by an arbitrary non-increasing function (specified by a value oracle) of its visiting time. Finally, we discuss applications of our results to variants of deadline TSP, including settings where both end-nodes are specified, nodes have release dates, and orienteering with time windows.

Subject Classification

ACM Subject Classification
  • Theory of computation → Approximation algorithms analysis
  • Mathematics of computing → Discrete optimization
Keywords
  • Approximation algorithms
  • Vehicle routing problems
  • Deadline TSP
  • Orienteering

Metrics

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

References

  1. H. C. An, R. Kleinberg, and D. B. Shmoys. Improving Christofides' algorithm for the s-t path TSP. Journal of the ACM, 62(5):34, 2015. Google Scholar
  2. N. Bansal, A. Blum, S. Chawla, and A. Meyerson. Approximation algorithms for deadline-TSP and vehicle routing with time windows. In Proceedings of 36th STOC, pages 166-174, 2004. Google Scholar
  3. A. Blum, S. Chawla, D. R. Karger, T. Lane, and A. Meyerson. Approximation algorithms for orienteering and discount-reward TSP. SIAM J. Comput., 37(2):653-670, 2007. Google Scholar
  4. R. Carr and S. Vempala. Randomized metarounding. Random Structures and Algorithms, 20(3):343-352, 2002. Google Scholar
  5. K. Chaudhuri, B. Godfrey, S. Rao, and K. Talwar. Paths, trees, and minimum latency tours. In Proceedings of 44th FOCS, pages 36-45, 2003. Google Scholar
  6. C. Chekuri, N. Korula, and M. Pál. Improved algorithms for orienteering and related problems. ACM Transactions on Algorithms, 8(3), 2012. Google Scholar
  7. C. Chekuri and A. Kumar. Maximum coverage problem with group budget constraints and applications. In Proceedings of 7th APPROX, pages 72-83, 2004. Google Scholar
  8. C. Chekuri and M. Pál. A recursive greedy algorithm for walks in directed graphs. In Proceedings of 46th FOCS, pages 245-253, 2005. Google Scholar
  9. N. Christofides. Worst-case analysis of a new heuristic for the traveling salesman problem. Technical Report 388, Graduate School of Industrial Administration, CMU, 1976. Google Scholar
  10. B. Farbstein and A. Levin. Discount reward TSP. Algorithmica, 80(2):472-495, 2018. Google Scholar
  11. L. Fleischer, M. Goemans, V. Mirrokni, and M. Sviridenko. Tight approximation algorithms for maximum general assignment problems. In Proceedings of 17th SODA, pages 611-620, 2006. Google Scholar
  12. Z. Friggstad, M. R. Salavatipour, and Z. Svitkina. Asymmetric traveling salesman path and directed latency problems. SIAM J. Comput, 42(4):1596-1619, 2013. Google Scholar
  13. Z. Friggstad and C. Swamy. Approximation algorithms for regret-bounded vehicle routing and applications to distance-constrained vehicle routing. In Proceedings of 46th STOC, pages 744-753, 2014. Detailed version posted on CS arXiv, Nov 2013. Google Scholar
  14. Z. Friggstad and C. Swamy. Compact, provably-good LPs for orienteering and regret-bounded vehicle routing. In Proceedings of 19th IPCO, pages 199-211, 2017. Google Scholar
  15. B. L. Golden, L. Levy, and R. Vohra. The orienteering problem. Naval Research Logistics, 34:307-318, 1987. Google Scholar
  16. E. Halperin and R. Krauthgamer. Polylogarithmic inapproximability. In Proceedings of 35th STOC, pages 585-594, 2003. Google Scholar
  17. A. Köhne, V. Traub, , and J. Vygen. The asymmetric traveling salesman path LP has constant integrality ratio. In Proceedings of 20th IPCO, pages 288-298, 2019. Google Scholar
  18. R. Lavi and C. Swamy. Truthful and near-optimal mechanism design via linear programming. Journal of the ACM, 58(6), 2011. Google Scholar
  19. C.-L. Li, D. Simchi-Levi, and M. Desrochers. On the distance constrained vehicle routing problem. Operations research, 40:790-799, 1992. Google Scholar
  20. V. Nagarajan and R. Ravi. The directed minimum latency problem. In Proceedings of 11th APPROX, pages 193-206, 2008. Google Scholar
  21. V. Nagarajan and R. Ravi. The directed orienteering problem. Algorithmica, 60(4):1017-1030, 2011. Google Scholar
  22. V. Nagarajan and R. Ravi. Approximation algorithms for distance constrained vehicle routing problems. Networks, 59(2):209-214, 2012. Google Scholar
  23. I. Post and C. Swamy. Linear-programming based techniques for multi-vehicle minimum latency problems. In Proceedings of 26th SODA, pages 512-531, 2015. Google Scholar
  24. A. Sebo and A. van Zuylen. The salesman’s improved paths: A 3/2 + 1/34 approximation. In Proceedings of 57th FOCS, pages 118-127, 2016. Google Scholar
  25. A. Sebo and J. Vygen. Shorter tours by nicer ears: 7/5-approximation for the graph-TSP, 3/2 for the path version, and 4/3 for two-edge-connected subgraphs. Combinatorica, 34(5):597-629, 2014. Google Scholar
  26. O. Svensson, J. Tarnawski, and L. Vegh. A constant-factor approximation algorithm for the asymmetric traveling salesman problem. In Proceedings of 50th STOC, pages 204-213, 2018. Google Scholar
  27. P. Toth and eds D. Vigo. The Vehicle Routing Problem. SIAM Monographs on Discrete Mathematics and Applications, Philadelphia, 2002. Google Scholar
  28. V. Traub and J. Vygen. Approaching 3/2 for the s-t path TSP. In Proceedings of 29th SODA, pages 1854-1864, 2018. Google Scholar
  29. R. Zenklusen. A 1.5-approximation for path TSP. In Proceedings of 30th SODA, pages 1539-1549, 2019. 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