Document Open Access Logo

A Constant-Factor Approximation for Directed Latency in Quasi-Polynomial Time

Authors Zachary Friggstad, Chaitanya Swamy

PDF
Thumbnail PDF

File

LIPIcs.ESA.2020.52.pdf
  • Filesize: 1.05 MB
  • 20 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

Funding

  • Friggstad, Zachary: Supported by the Canada Research Chairs program and an NSERC Discovery grant.
  • Swamy, Chaitanya: Supported in part by NSERC grant 327620-09 and an NSERC Discovery Accelerator Supplement Award.

Cite As Get BibTex

Zachary Friggstad and Chaitanya Swamy. A Constant-Factor Approximation for Directed Latency in Quasi-Polynomial Time. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 52:1-52:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.ESA.2020.52

Abstract

We consider the directed minimum latency problem (DirLat), wherein we seek a path P visiting all points (or clients) in a given asymmetric metric starting at a given root node r, so as to minimize the sum of the client waiting times, where the waiting time of a client v is the length of the r-v portion of P. We give the first constant-factor approximation guarantee for DirLat, but in quasi-polynomial time. Previously, a polynomial-time O(log n)-approximation was known [Z. Friggstad et al., 2013], and no better approximation guarantees were known even in quasi-polynomial time. 
A key ingredient of our result, and our chief technical contribution, is an extension of a recent result of [A. Köhne et al., 2019] showing that the integrality gap of the natural Held-Karp relaxation for asymmetric TSP-Path (ATSPP) is at most a constant, which itself builds on the breakthrough similar result established for asymmetric TSP (ATSP) by Svensson et al. [O. Svensson et al., 2018]. We show that the integrality gap of the Held-Karp relaxation for ATSPP is bounded by a constant even if the cut requirements of the LP relaxation are relaxed from x(δ^{in}(S)) ≥ 1 to x(δ^{in}(S)) ≥ ρ for some constant 1/2 < ρ ≤ 1. 
We also give a better approximation guarantee for the minimum total-regret problem, where the goal is to find a path P that minimizes the total time that nodes spend in excess of their shortest-path distances from r, which can be cast as a special case of DirLat involving so-called regret metrics.

Subject Classification

ACM Subject Classification
  • Theory of computation → Approximation algorithms analysis
Keywords
  • Approximation Algorithms
  • Directed Latency
  • TSP

Metrics

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

Related Versions

References

  1. F. Afrati, S. Cosmadakis, C. H. Papadimitriou, G. Papageorgiou, and N. Papakostantinou. The complexity of the traveling repairman problem. Informatique Theorique et Applications, 20(1):79-87, 1986. Google Scholar
  2. 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
  3. A. Asadpour, M. X. Goemans, A. Madry, S. Oveis Gharan, and A. Saberi. An O(log n / log log n)-approximation algorithm for the asymmetric traveling salesman problem. In In Proceedings of SODA, pages 379-389, 2010. Google Scholar
  4. J. Bang-Jensen, A. Frank, and B. Jackson. Preserving and increasing local edge-connectivity in mixed graphs. SIAM J. Discrete Math., 8(2):155-178, 1995. Google Scholar
  5. A. Blum, P. Chalasani, D. Coppersmith, W. R. Pulleyblank, P. Raghavan, and M. Sudan. The minimum latency problem. In In Proceedings of STOC, pages 163-171, 1994. Google Scholar
  6. 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
  7. D. Chakrabarty and C. Swamy. Facility location with client latencies: linear-programming based techniques for minimum latency problems. Math. of Operations Research, 41(3):865-883, 2016. Google Scholar
  8. M. Charikar, M. X. Goemans, and H. J. Karloff. On the integrality ratio for the asymmetric traveling salesman problem. Math. of Operations Research, 31(2):245-252, 2006. Google Scholar
  9. K. Chaudhuri, B. Godfrey, S. Rao, and K. Talwar. Paths, trees, and minimum latency tours. In In Proceedings of FOCS, pages 36-45, 2003. Google Scholar
  10. M. Fischetti, G. Laporte, and S. Martello. The delivery man problem and cumulative matroids. Operations Research, 41:1065-1064, 1993. Google Scholar
  11. Z. Friggstad, A. Gupta, and M. Singh. An improved integrality gap for asymmetric TSP paths. Math. of Operations Research, 41(3):745-757, 2016. 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 In Proceedings of STOC, pages 744-753, 2014. Google Scholar
  14. Z. Friggstad and C. Swamy. Compact, provably-good LPs for orienteering and regret-bounded vehicle routing. In In Proceedings of IPCO, pages 199-211, 2017. Google Scholar
  15. H. Gabow. Perfect arborescence packing in preflow mincut graphs. In In Proceedings of SODA, pages 528-538, 1996. Google Scholar
  16. M. X. Goemans and D. P. Williamson. Approximating minimum-cost graph problems with spanning tree edges. Operations Research Letters, 16:183-189, 1994. Google Scholar
  17. A. Köhne, V. Traub, , and J. Vygen. The asymmetric traveling salesman path LP has constant integrality ratio. In In Proceedings of IPCO, pages 288-298, 2019. Google Scholar
  18. W. Mader. Konstruktion aller n-fach kantenzusammenhängenden Digraphen. Europ. J. Combinatorics, 3:63-67, 1982. Google Scholar
  19. E. Minieka. The delivery man problem on a tree network. Annals of Operations Res., 18:261-266, 1989. Google Scholar
  20. V. Nagarajan and R. Ravi. The directed minimum latency problem. In APPROX/RANDOM 2008. Proceedings, Lecture Notes in Computer Science, pages 193-206. Springer, 2008. Google Scholar
  21. J. Park and B. Kim. The school bus routing problem: A review. European Journal of Operational Research, 202(2):311-319, 2010. Google Scholar
  22. I. Post and C. Swamy. Linear-programming based techniques for multi-vehicle minimum latency problems. In Proceedings of SODA, pages 512-531, 2015. Google Scholar
  23. M. Skutella. List scheduling in order of α-points on a single machine. Efficient Approximation and Online Algorithms, 3484:250-291, 2006. Google Scholar
  24. M. Spada, M. Bierlaire, and T. Liebling. Decision-aiding methodology for the school bus routing and scheduling problem. Transportation Science, 39(4):477-490, 2005. Google Scholar
  25. O. Svensson, J. Tarnawski, and L. Vegh. A constant-factor approximation algorithm for the asymmetric traveling salesman problem. In In Proceedings of STOC, pages 204-213, 2018. Google Scholar
  26. P. Toth and eds D. Vigo. The Vehicle Routing Problem. SIAM Monographs on Discrete Mathematics and Applications, Philadelphia, 2002. Google Scholar
  27. V. Traub. Approximation Algorithms for Traveling Salesman Problems. PhD thesis, University of Bonn, 2020. URL: http://hss.ulb.uni-bonn.de/2020/5834/5834.htm.
  28. V. Traub and J. Vygen. An improved approximation algorithm for ATSP. In In Proceedings of STOC, pages 1-13, 2020. 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
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact