• français
    • English
  • français 
    • français
    • English
  • Connexion
JavaScript is disabled for your browser. Some features of this site may not work without it.
Accueil

Afficher

Cette collectionPar Date de CréationAuteursTitresSujetsNoms de revueToute la baseCentres de recherche & CollectionsPar Date de CréationAuteursTitresSujetsNoms de revue

Mon compte

Connexion

Statistiques

Afficher les statistiques d'usage

Differential approximation for some routing problems

Thumbnail
Date
2003
Indexation documentaire
Recherche opérationnelle
Subject
approximation algorithm; differential ratio; VRP; TSP
Réf version publiée
http://dx.doi.org/10.1007/3-540-44849-7_31
Pays du colloque
ITALY
Titre de l'ouvrage
Algorithms and Complexity 5th Italian Conference, CIAC 2003, Rome, Italy, May 28-30, 2003, Proceedings
Auteur
Silvestri, Riccardo
Nom de l'éditeur
Springer
Ville de l'éditeur
Berlin Heidelberg
Année
2003
ISBN
978-3-540-40176-6
URL de l'ouvrage
10.1007/3-540-44849-7
URI
https://basepub.dauphine.fr/handle/123456789/5793
Collections
  • LAMSADE : Publications
Métadonnées
Afficher la notice complète
Auteur
Bazgan, Cristina
Hassin, Refael
Monnot, Jérôme
Type
Communication / Conférence
Nombre de pages du document
277-288
Résumé en anglais
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.

  • Accueil Bibliothèque
  • Site de l'Université Paris-Dauphine
  • Contact
SCD Paris Dauphine - Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16

 Cette création est mise à disposition sous un contrat Creative Commons.