Document Open Access Logo

Polynomial-Time Approximation Schemes for k-center, k-median, and Capacitated Vehicle Routing in Bounded Highway Dimension

Authors Amariah Becker, Philip N. Klein, David Saulpic

PDF
Thumbnail PDF

File

LIPIcs.ESA.2018.8.pdf
  • Filesize: 0.84 MB
  • 15 pages

Document Identifiers

Author Details

Amariah Becker
  • Department of Computer Science, Brown University
Philip N. Klein
  • Department of Computer Science, Brown University
David Saulpic
  • Département d'Informatique, École Normale Supérieure

Funding

Research supported by National Science Foundation grant CCF-1409520.

Cite AsGet BibTex

Amariah Becker, Philip N. Klein, and David Saulpic. Polynomial-Time Approximation Schemes for k-center, k-median, and Capacitated Vehicle Routing in Bounded Highway Dimension. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 8:1-8:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.ESA.2018.8

Abstract

The concept of bounded highway dimension was developed to capture observed properties of road networks. We show that a graph of bounded highway dimension with a distinguished root vertex can be embedded into a graph of bounded treewidth in such a way that u-to-v distance is preserved up to an additive error of epsilon times the u-to-root plus v-to-root distances. We show that this embedding yields a PTAS for Bounded-Capacity Vehicle Routing in graphs of bounded highway dimension. In this problem, the input specifies a depot and a set of clients, each with a location and demand; the output is a set of depot-to-depot tours, where each client is visited by some tour and each tour covers at most Q units of client demand. Our PTAS can be extended to handle penalties for unvisited clients. We extend this embedding result to handle a set S of root vertices. This result implies a PTAS for Multiple Depot Bounded-Capacity Vehicle Routing: the tours can go from one depot to another. The embedding result also implies that, for fixed k, there is a PTAS for k-Center in graphs of bounded highway dimension. In this problem, the goal is to minimize d so that there exist k vertices (the centers) such that every vertex is within distance d of some center. Similarly, for fixed k, there is a PTAS for k-Median in graphs of bounded highway dimension. In this problem, the goal is to minimize the sum of distances to the k centers.

Subject Classification

ACM Subject Classification
  • Theory of computation → Routing and network design problems
Keywords
  • Highway Dimension
  • Capacitated Vehicle Routing
  • Graph Embeddings

Metrics

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

Related Versions

References

  1. Ittai Abraham, Daniel Delling, Amos Fiat, Andrew V Goldberg, and Renato F Werneck. VC-dimension and shortest path algorithms. In International Colloquium on Automata, Languages, and Programming, pages 690-699. Springer, 2011. Google Scholar
  2. Ittai Abraham, Daniel Delling, Amos Fiat, Andrew V. Goldberg, and Renato F. Werneck. Highway dimension and provably efficient shortest path algorithms. Journal of the ACM, 63(5):41:1-41:26, 2016. Google Scholar
  3. Ittai Abraham, Amos Fiat, Andrew V Goldberg, and Renato F Werneck. Highway dimension, shortest paths, and provably efficient algorithms. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 782-793. SIAM, 2010. Google Scholar
  4. Anna Adamaszek, Artur Czumaj, and Andrzej Lingas. PTAS for k-tour cover problem on the plane for moderately large values of k. International Journal of Foundations of Computer Science, 21(6):893-904, 2010. URL: http://dx.doi.org/10.1142/S0129054110007623.
  5. Sanjeev Arora, Prabhakar Raghavan, and Satish Rao. Approximation schemes for Euclidean k-medians and related problems. In Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing (STOC), pages 106-113, 1998. Google Scholar
  6. Vijay Arya, Naveen Garg, Rohit Khandekar, Adam Meyerson, Kamesh Munagala, and Vinayaka Pandit. Local search heuristics for k-median and facility location problems. SIAM Journal on Computing, 33(3):544-562, 2004. Google Scholar
  7. Tetsuo Asano, Naoki Katoh, and Kazuhiro Kawashima. A new approximation algorithm for the capacitated vehicle routing problem on a tree. Journal of Combinatorial Optimization, 5(2):213-231, 2001. Google Scholar
  8. Tetsuo Asano, Naoki Katoh, Hisao Tamaki, and Takeshi Tokuyama. Covering points in the plane by k-tours: a polynomial approximation scheme for fixed k. IBM Tokyo Research Laboratory Research Report RT0162, 1996. Google Scholar
  9. Tetsuo Asano, Naoki Katoh, Hisao Tamaki, and Takeshi Tokuyama. Covering points in the plane by k-tours: towards a polynomial time approximation scheme for general k. In Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, pages 275-283, 1997. Google Scholar
  10. M. Bădoiu, S. Har-Peled, and P. Indyk. Approximate clustering via core-sets. In Proceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC), pages 250-257, 2002. Google Scholar
  11. H. Bast, Stefan Funke, and Domagoj Matijevic. Ultrafast shortest-path queries via transit nodes. In Camil Demetrescu, Andrew V. Goldberg, and David S. Johnson, editors, The Shortest Path Problem: Ninth DIMACS Implementation Challenge, volume 74 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pages 175-192. American Mathematical Society, 2009. Google Scholar
  12. H. Bast, Stefan Funke, Domagoj Matijevic, Peter Sanders, and Dominik Schultes. In transit to constant time shortest-path queries in road networks. In Proceedings of the Ninth Workshop on Algorithm Engineering and Experiments (ALENEX), pages 46-59. SIAM, 2007. Google Scholar
  13. Amariah Becker, Philip N. Klein, and David Saulpic. Polynomial-time approximation schemes for k-center and bounded-capacity vehicle routing in metrics with bounded highway dimension. arXiv:1707.08270, 2017. Google Scholar
  14. Amariah Becker, Philip N Klein, and David Saulpic. A quasi-polynomial-time approximation scheme for vehicle routing on planar and bounded-genus graphs. In 25th Annual European Symposium on Algorithms (ESA), volume 87, pages 12:1-12:15, 2017. Google Scholar
  15. Jaroslaw Byrka, Thomas Pensyl, Bartosz Rybicki, Aravind Srinivasan, and Khoa Trinh. An improved approximation for k-median and positive correlation in budgeted optimization. ACM Transactions on Algorithms, 13(2), 2017. Google Scholar
  16. Vincent Cohen-Addad, Philip N. Klein, and Claire Mathieu. Local search yields approximation schemes for k-means and k-median in Euclidean and minor-free metrics. In Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2016. Google Scholar
  17. Aparna Das and Claire Mathieu. A quasipolynomial-time approximation scheme for Euclidean capacitated vehicle routing. Algorithmica, 73(1):115-142, 2015. Google Scholar
  18. Tomás Feder and Daniel Greene. Optimal algorithms for approximate clustering. In Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing (STOC), 1988. Google Scholar
  19. Andreas Emil Feldmann. Fixed parameter approximations for k-center problems in low highway dimension graphs. In Proceedings, Part II, of the 42nd International Colloquium on Automata, Languages, and Programming (ICALP), pages 588-600. Springer-Verlag, 2015. Google Scholar
  20. Andreas Emil Feldmann, Wai Shing Fung, Jochen Könemann, and Ian Post. A (1+ε)-embedding of low highway dimension graphs into bounded treewidth graphs. In Proceedings, Part I, of the International Colloquium on Automata, Languages, and Programming (ICALP), pages 469-480. Springer, 2015. Google Scholar
  21. Bruce L Golden and Richard T Wong. Capacitated arc routing problems. Networks, 11(3):305-315, 1981. Google Scholar
  22. Teofilo F Gonzalez. Clustering to minimize the maximum intercluster distance. Theoretical Computer Science, 38:293-306, 1985. Google Scholar
  23. Sudipto Guha and Samir Khuller. Greedy strikes back: Improved facility location algorithms. Journal of Algorithms, 31(1):228-248, 1999. Google Scholar
  24. Anupam Gupta, Robert Krauthgamer, and James R Lee. Bounded geometries, fractals, and low-distortion embeddings. In Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 534-543. IEEE, 2003. Google Scholar
  25. Venkatesan Guruswami and Piotr Indyk. Embeddings and non-approximability of geometric problems. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 2003. Google Scholar
  26. Mark Haimovich and A. H. G. Rinnooy Kan. Bounds and heuristics for capacitated routing problems. Mathematics of Operations Research, 10(4):527-542, 1985. Google Scholar
  27. Shin Hamaguchi and Naoki Katoh. A capacitated vehicle routing problem on a tree. In International Symposium on Algorithms and Computation, pages 399-407. Springer, 1998. Google Scholar
  28. Dorit S Hochbaum and David B Shmoys. A best possible heuristic for the k-center problem. Mathematics of Operations Research, 10(2):180-184, 1985. Google Scholar
  29. Kamal Jain and Vijay V. Vazirani. Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and Lagrangian relaxation. Journal of the ACM, 48(2):274-296, 2001. Google Scholar
  30. Michael Khachay and Roman Dubinin. PTAS for the Euclidean capacitated vehicle routing problem in ℝ^d. In Proceedings of the 9th International Conference on Discrete Optimization and Operations Research (DOOR), pages 193-205. Springer, 2016. Google Scholar
  31. Ján Plesník. On the computational complexity of centers located in a graph. Aplikace matematiky, 25(6):445-452, 1980. Google Scholar
  32. David B Shmoys, Éva Tardos, and Karen Aardal. Approximation algorithms for facility location problems. In Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, pages 265-274. ACM, 1997. 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 Imprint Privacy Contact