
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
Type
Communication / ConférenceDate
2008Conference country
AUSTRALIABook title
ISAAC 2008, 19th International Symposium on Algorithms and ComputationBook author
Nagamochi, HiroshiPublisher
Springer
Published in
Berlin Heidelberg
ISBN
978-3-540-92181-3
Pages
945
Metadata
Show full item recordAbstract (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 ProblemRelated items
Showing items related by title and author.
-
Couëtoux, Basile; Gourvès, Laurent; Monnot, Jérôme; Telelis, Orestis (2010) Article accepté pour publication ou publié
-
Gourvès, Laurent; Monnot, Jérôme; Telelis, Orestis (2012) Chapitre d'ouvrage
-
Telelis, Orestis; Monnot, Jérôme; Gourvès, Laurent (2009) Communication / Conférence
-
Chatti, Hatem; Monnot, Jérôme; Gourvès, Laurent (2010) Communication / Conférence
-
Couëtoux, Basile; Monnot, Jérôme; Toubaline, Sónia (2012) Communication / Conférence