On Labeled Traveling Salesman Problems: 19th International Symposium, ISAAC 2008, Gold Coast, Australia, December 15-17, 2008. Proceedings

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperConference articleResearchpeer-review

  • Basile Couetoux, University Paris-Dauphine, France
  • Laurent Gourves, LAMSADE CNRS UMR 7024, University Paris-Dauphine, France
  • Jerome Monnot, LAMSADE CNRS UMR 7024, University Paris-Dauphine, France
  • Orestis A. Telelis, Denmark
  • Department of Computer Science
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.
Original languageEnglish
Book seriesLecture Notes in Computer Science
Pages (from-to)776-787
Number of pages12
Publication statusPublished - 2008
EventAlgorithms and Computation, 19th International Symposium, ISAAC 2008 - Gold Coast, Australia
Duration: 15 Dec 200817 Dec 2008
Conference number: 19


ConferenceAlgorithms and Computation, 19th International Symposium, ISAAC 2008
CityGold Coast

See relations at Aarhus University Citationformats

ID: 14991136