• 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

On Labeled Traveling Salesman Problems

Thumbnail
View/Open
TravelingSalesman.PDF (192.0Kb)
Date
2008
Dewey
Recherche opérationnelle
Sujet
APX-hardness; approximation algorithms; Traveling Salesman Problem
Conference country
AUSTRALIA
Book title
ISAAC 2008, 19th International Symposium on Algorithms and Computation
Author
Nagamochi, Hiroshi
Publisher
Springer
Publisher city
Berlin Heidelberg
Year
2008
ISBN
978-3-540-92181-3
URI
https://basepub.dauphine.fr/handle/123456789/4785
Collections
  • LAMSADE : Publications
Metadata
Show full item record
Author
Couëtoux, Basile
Gourvès, Laurent
Monnot, Jérôme
Telelis, Orestis
Type
Communication / Conférence
Item number of pages
945
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.

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