• 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

On Labeled Traveling Salesman Problems

Couëtoux, Basile; Gourvès, Laurent; Monnot, Jérôme; Telelis, Orestis (2008), On Labeled Traveling Salesman Problems, in Nagamochi, Hiroshi, ISAAC 2008, 19th International Symposium on Algorithms and Computation, Springer : Berlin Heidelberg, p. 945

View/Open
TravelingSalesman.PDF (192.0Kb)
Type
Communication / Conférence
Date
2008
Conference country
AUSTRALIA
Book title
ISAAC 2008, 19th International Symposium on Algorithms and Computation
Book author
Nagamochi, Hiroshi
Publisher
Springer
Published in
Berlin Heidelberg
ISBN
978-3-540-92181-3
Pages
945
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 $\frac{1}{2}$-approximation algorithm and show that it is APX-hard. For the minimization version, we show that it is not approximable within n 1 − ε for every ε> 0. When every color appears in the graph at most r times and r is an increasing function of n the problem is not O(r 1 − ε )-approximable. For fixed constant r we analyze a polynomial-time (r + H r )/2-approximation algorithm (H r is the r-th harmonic number), and prove APX-hardness. Analysis of the studied algorithms is shown to be tight.
Subjects / Keywords
APX-hardness; approximation algorithms; Traveling Salesman Problem

Related items

Showing items related by title and author.

  • Thumbnail
    Labeled Traveling Salesman Problems: Complexity and approximation 
    Couëtoux, Basile; Gourvès, Laurent; Monnot, Jérôme; Telelis, Orestis (2010) Article accepté pour publication ou publié
  • Thumbnail
    Strategic Scheduling Games: Equilibria and Efficiency 
    Gourvès, Laurent; Monnot, Jérôme; Telelis, Orestis (2012) Chapitre d'ouvrage
  • Thumbnail
    Selfish scheduling with setup times 
    Telelis, Orestis; Monnot, Jérôme; Gourvès, Laurent (2009) Communication / Conférence
  • Thumbnail
    On a Labeled Vehicle Routing Problem 
    Chatti, Hatem; Monnot, Jérôme; Gourvès, Laurent (2010) Communication / Conférence
  • Thumbnail
    Complexity Results for the Empire Problem in Collection of Stars 
    Couëtoux, Basile; Monnot, Jérôme; Toubaline, Sónia (2012) 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