• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail - Request a copy

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érence
Date
2003
Conference country
ITALY
Book title
Algorithms and Complexity 5th Italian Conference, CIAC 2003, Rome, Italy, May 28-30, 2003, Proceedings
Book author
Silvestri, Riccardo
Publisher
Springer
Published in
Berlin Heidelberg
ISBN
978-3-540-40176-6
Pages
277-288
Publication identifier
10.1007/3-540-44849-7_31
Metadata
Show full item record
Author(s)
Bazgan, Cristina
Hassin, Refael
Monnot, Jérôme cc
Abstract (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; TSP

Related items

Showing items related by title and author.

  • Thumbnail
    Approximation algorithms for some vehicle routing problems 
    Bazgan, Cristina; Monnot, Jérôme; Hassin, Refael (2005) Article accepté pour publication ou publié
  • Thumbnail
    Approximation algorithms and hardness results for labeled connectivity problems 
    Hassin, Refael; Monnot, Jérôme; Segev, Danny (2007) Article accepté pour publication ou publié
  • Thumbnail
    Approximation Algorithms and Hardness Results for Labeled Connectivity Problems 
    Hassin, Refael; Monnot, Jérôme; Segev, Danny (2006) Communication / Conférence
  • Thumbnail
    Approximation with a Fixed Number of Solutions of Some Biobjective Maximization Problems 
    Bazgan, Cristina; Gourvès, Laurent; Monnot, Jérôme (2012) Communication / Conférence
  • Thumbnail
    Approximation with a fixed number of solutions of some multiobjective maximization problems 
    Bazgan, Cristina; Gourvès, Laurent; Monnot, Jérôme (2013) Article accepté pour publication ou publié
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo