• 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

Labeled Traveling Salesman Problems: Complexity and approximation

Couëtoux, Basile; Gourvès, Laurent; Monnot, Jérôme; Telelis, Orestis (2010), Labeled Traveling Salesman Problems: Complexity and approximation, Discrete Optimization, 7, 1-2, p. 74-85. http://dx.doi.org/10.1016/j.disopt.2010.02.003

View/Open
ltsp.pdf (225.9Kb)
Type
Article accepté pour publication ou publié
Date
2010
Journal name
Discrete Optimization
Volume
7
Number
1-2
Publisher
Elsevier
Pages
74-85
Publication identifier
http://dx.doi.org/10.1016/j.disopt.2010.02.003
Metadata
Show full item record
Author(s)
Couëtoux, Basile
Gourvès, Laurent
Monnot, Jérôme cc
Telelis, Orestis
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.
Subjects / Keywords
Approximation algorithms; Hamilton tour; Traveling Salesman Problem; Edge-colored graphs; Complexity

Related items

Showing items related by title and author.

  • Thumbnail
    On Labeled Traveling Salesman Problems 
    Couëtoux, Basile; Gourvès, Laurent; Monnot, Jérôme; Telelis, Orestis (2008) Communication / Conférence
  • Thumbnail
    Strategic Scheduling Games: Equilibria and Efficiency 
    Gourvès, Laurent; Monnot, Jérôme; Telelis, Orestis (2012) Chapitre d'ouvrage
  • Thumbnail
    Complexity and Approximation Results for the Connected Vertex Cover Problem in Graphs and Hypergraphs 
    Monnot, Jérôme; Gourvès, Laurent; Escoffier, Bruno (2010) Article accepté pour publication ou publié
  • Thumbnail
    Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs 
    Escoffier, Bruno; Gourvès, Laurent; Monnot, Jérôme (2007) Document de travail / Working paper
  • Thumbnail
    Selfish scheduling with setup times 
    Telelis, Orestis; Monnot, Jérôme; Gourvès, Laurent (2009) Communication / Conférence
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