LIPIcs.APPROX-RANDOM.2018.3.pdf
- Filesize: 0.66 MB
- 15 pages
Document
A Tight 4/3 Approximation for Capacitated Vehicle Routing in Trees
Author
-
Part of:
Volume:
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Conference on Randomization and Computation (RANDOM)
Conference: International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2018-08-13
Cite As Get BibTex
Amariah Becker. A Tight 4/3 Approximation for Capacitated Vehicle Routing in Trees. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 116, pp. 3:1-3:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2018.3
Abstract
Given a set of clients with demands, the Capacitated Vehicle Routing problem is to find a set of tours that collectively cover all client demand, such that the capacity of each vehicle is not exceeded and such that the sum of the tour lengths is minimized. In this paper, we provide a 4/3-approximation algorithm for Capacitated Vehicle Routing on trees, improving over the previous best-known approximation ratio of (sqrt{41}-1)/4 by Asano et al.[Asano et al., 2001], while using the same lower bound. Asano et al. show that there exist instances whose optimal cost is 4/3 times this lower bound. Notably, our 4/3 approximation ratio is therefore tight for this lower bound, achieving the best-possible performance.
Subject Classification
ACM Subject Classification
- Theory of computation → Routing and network design problems
Keywords
- Approximation algorithms
- Graph algorithms
- Capacitated vehicle routing
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
Kemal Altinkemer and Bezalel Gavish. Heuristics for unequal weight delivery problems with a fixed error guarantee. Operations Research Letters, 6(4):149-158, 1987.
-
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.
-
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. ACM, 1997.
-
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 preprint arXiv:1707.08270, 2017.
-
Amariah Becker, Philip N Klein, and David Saulpic. A quasi-polynomial-time approximation scheme for vehicle routing on planar and bounded-genus graphs. In LIPIcs-Leibniz International Proceedings in Informatics, volume 87. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017.
-
Nicos Christofides. Worst-case analysis of a new heuristic for the travelling salesman problem. Technical report, Carnegie-Mellon Univ Pittsburgh Pa Management Sciences Research Group, 1976.
-
Aparna Das and Claire Mathieu. A quasi-polynomial time approximation scheme for Euclidean capacitated vehicle routing. In Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms, pages 390-403. SIAM, 2010.
-
Bruce L Golden and Richard T Wong. Capacitated arc routing problems. Networks, 11(3):305-315, 1981.
-
Mark Haimovich and AHG Rinnooy Kan. Bounds and heuristics for capacitated routing problems. Mathematics of operations Research, 10(4):527-542, 1985.
-
Shin-ya Hamaguchi and Naoki Katoh. A capacitated vehicle routing problem on a tree. In International Symposium on Algorithms and Computation, pages 399-407. Springer, 1998.
-
Michael Khachay and Roman Dubinin. PTAS for the Euclidean capacitated vehicle routing problem in ℝ^d. In International Conference on Discrete Optimization and Operations Research, pages 193-205. Springer, 2016.
-
Martine Labbé, Gilbert Laporte, and Hélene Mercure. Capacitated vehicle routing on trees. Operations Research, 39(4):616-622, 1991.
-
Christos H Papadimitriou and Mihalis Yannakakis. The traveling salesman problem with distances one and two. Mathematics of Operations Research, 18(1):1-11, 1993.