Differential approximation for some routing problems
Bazgan, Cristina; Hassin, Refael; Monnot, Jérôme (2003), Differential approximation for some routing problems, in Silvestri, Riccardo, Algorithms and Complexity 5th Italian Conference, CIAC 2003, Rome, Italy, May 28-30, 2003, Proceedings, Springer : Berlin Heidelberg, p. 277-288. 10.1007/3-540-44849-7_31
Type
Communication / ConférenceDate
2003Conference country
ITALYBook title
Algorithms and Complexity 5th Italian Conference, CIAC 2003, Rome, Italy, May 28-30, 2003, ProceedingsBook author
Silvestri, RiccardoPublisher
Springer
Published in
Berlin Heidelberg
ISBN
978-3-540-40176-6
Pages
277-288
Publication identifier
Metadata
Show full item recordAbstract (EN)
We study vehicle routing problems with constraints on the distance traveled by each vehicle or on the number of vehicles. The objective is to minimize the total distance traveled by vehicles. We design constant differential approximation algorithms for some of these problems. In particular we obtain differential bounds: $ \frac{1} {2} $21 for Metric 3VRP, $ \frac{3} {5} $53 for Metric 4VRP, $ \frac{2} {3} $32 for Metric kVRP with k ≥ 5, $ \frac{1} {2} $21 for the nonmetric case for any k ≥ 3, and 1/3 for Constrained VRP. We prove also that Min-Sum EkTSP is $ \frac{2} {3} $32 differential approximable and has no differential approximation scheme, unless P = NP.Subjects / Keywords
approximation algorithm; differential ratio; VRP; TSPRelated items
Showing items related by title and author.
-
Bazgan, Cristina; Monnot, Jérôme; Hassin, Refael (2005) Article accepté pour publication ou publié
-
Hassin, Refael; Monnot, Jérôme; Segev, Danny (2007) Article accepté pour publication ou publié
-
Hassin, Refael; Monnot, Jérôme; Segev, Danny (2006) Communication / Conférence
-
Bazgan, Cristina; Gourvès, Laurent; Monnot, Jérôme (2012) Communication / Conférence
-
Bazgan, Cristina; Gourvès, Laurent; Monnot, Jérôme (2013) Article accepté pour publication ou publié