• 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

A Better differential approximation ratio for symmetric TSP

Thumbnail
Ouvrir
cahierLamsade261.pdf (338.1Kb)
Date
2008
Description
Version préliminaire dans Cahiers du LAMSADE N° 261
Indexation documentaire
Programmation, logiciels, organisation des données
Subject
Traveling salesman problem; Differential ratio; Approximation algorithm
Nom de la revue
Theoretical Computer Science
Volume
396
Numéro
1-3
Date de publication
05-2008
Pages article
63-70
Nom de l'éditeur
Elsevier
DOI
http://dx.doi.org/10.1016/j.tcs.2008.01.002
URI
https://basepub.dauphine.fr/handle/123456789/1542
Collections
  • LAMSADE : Publications
Métadonnées
Afficher la notice complète
Auteur
Escoffier, Bruno
Monnot, Jérôme
Type
Article accepté pour publication ou publié
Résumé en anglais
In this paper, we study the approximability properties of symmetric TSP under an approximation measure called the differential ratio. More precisely, we improve up to 3/4−ε (for any ε>0) the best differential ratio of 2/3 known so far, given in Hassin and Khuller, [R. Hassin, S. Khuller, z-approximations, J. Algorithms, 41 (2) (2001) 429–442].

  • 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.