Single Approximation for Biobjective Max TSP

Thumbnail
Date
2012
Indexation documentaire
Recherche opérationnelle
Subject
Hamiltonian cycle; Single Approximation
Réf version publiée
http://dx.doi.org/10.1007/978-3-642-29116-6_5
Titre du colloque
9th International Workshop on Approximation and Online Algorithms, WAOA 2011
Date du colloque
09-2011
Ville du colloque
Saarbrücken
Pays du colloque
Germany
Titre de l'ouvrage
Approximation and Online Algorithms 9th International Workshop, WAOA 2011, Saarbrücken, Germany, September 8-9, 2011, Revised Selected Papers
Auteur
Solis-Oba, Roberto
Nom de l'éditeur
Springer
Ville de l'éditeur
Berlin Heidelberg
Année
2012
ISBN
978-3-642-29115-9
URL de l'ouvrage
http://dx.doi.org/10.1007/978-3-642-29116-6
URI
https://basepub.dauphine.fr/handle/123456789/9034
Collections
Métadonnées
Afficher la notice complète
Auteur
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
Nombre de pages du document
49-62
Résumé en anglais
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.