Single Approximation for Biobjective Max TSP

Thumbnail
Date
2012
Dewey
Recherche opérationnelle
Sujet
Hamiltonian cycle; Single Approximation
DOI
http://dx.doi.org/10.1007/978-3-642-29116-6_5
Conference name
9th International Workshop on Approximation and Online Algorithms, WAOA 2011
Conference date
09-2011
Conference city
Saarbrücken
Conference country
Germany
Book title
Approximation and Online Algorithms 9th International Workshop, WAOA 2011, Saarbrücken, Germany, September 8-9, 2011, Revised Selected Papers
Author
Solis-Oba, Roberto
Publisher
Springer
Publisher city
Berlin Heidelberg
Year
2012
ISBN
978-3-642-29115-9
Book URL
http://dx.doi.org/10.1007/978-3-642-29116-6
URI
https://basepub.dauphine.fr/handle/123456789/9034
Collections
Metadata
Show full item record
Author
Bazgan, Cristina
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Gourvès, Laurent
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Monnot, Jérôme
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Pascual, Fanny
233 Laboratoire d'Informatique de Paris 6 [LIP6]
Type
Communication / Conférence
Item number of pages
49-62
Abstract (EN)
We propose an algorithm which returns a single Hamiltonian cycle with performance guarantee on both objectives. The algorithm is analysed in three cases. When both (resp. at least one) objective function(s) fulfill(s) the triangle inequality, the approximation ratio is 512−041 (resp. 83−). When the triangle inequality is not assumed on any objective function, the algorithm is 141+22−027 -approximate.