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

Browse

This CollectionBy Issue DateAuthorsTitlesSubjectsJournals BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesSubjectsJournals

My Account

Login

Statistics

View Usage Statistics

Labeled Traveling Salesman Problems: Complexity and approximation

Thumbnail
View/Open
ltsp.pdf (225.9Kb)
Date
2010
Dewey
Recherche opérationnelle
Sujet
Approximation algorithms; Hamilton tour; Traveling Salesman Problem; Edge-colored graphs; Complexity
Journal issue
Discrete Optimization
Volume
7
Number
1-2
Publication date
2010
Article pages
74-85
Publisher
Elsevier
DOI
http://dx.doi.org/10.1016/j.disopt.2010.02.003
URI
https://basepub.dauphine.fr/handle/123456789/12456
Collections
  • LAMSADE : Publications
Metadata
Show full item record
Author
Couëtoux, Basile
Gourvès, Laurent
Monnot, Jérôme
Telelis, Orestis
Type
Article accepté pour publication ou publié
Abstract (EN)
We consider labeled Traveling Salesman Problems, defined upon a complete graph of n vertices with colored edges. The objective is to find a tour of maximum or minimum number of colors. We derive results regarding hardness of approximation and analyze approximation algorithms, for both versions of the problem. For the maximization version we give a View the MathML source-approximation algorithm based on local improvements and show that the problem is APX-hard. For the minimization version, we show that it is not approximable within n1−ϵ for any fixed ϵ>0. When every color appears in the graph at most r times and r is an increasing function of n, the problem is shown not to be approximable within factor O(r1−ϵ). For fixed constant r we analyze a polynomial-time (r+Hr)/2-approximation algorithm, where Hr is the rth harmonic number, and prove APX-hardness for r=2. For all of the analyzed algorithms we exhibit tightness of their analysis by provision of appropriate worst-case instances.

  • 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

 Content on this site is licensed under a Creative Commons 2.0 France (CC BY-NC-ND 2.0) license.