Thumbnail

Single approximation for biobjective Max TSP

Bazgan, Cristina; Gourvès, Laurent; Monnot, Jérôme; Pascual, Fanny (2013), Single approximation for biobjective Max TSP, Theoretical Computer Science, 478, p. 41-50. http://dx.doi.org/10.1016/j.tcs.2013.01.021

View/Open
Type
Article accepté pour publication ou publié
Date
2013
Journal name
Theoretical Computer Science
Volume
478
Publisher
Elsevier
Pages
41-50
Publication identifier
Metadata
Show full item record
Author(s)
Bazgan, Cristina
Gourvès, Laurent
Monnot, Jérôme cc
Pascual, Fanny
Abstract (EN)
We mainly study the Max TSP with two objective functions. We propose an algorithm which returns a single Hamiltonian cycle with performance guarantee on both objectives. The algorithm is analyzed in three cases. When both (respectively, at least one) objective function(s) fulfill(s) the triangle inequality, the approximation ratio is View the MathML source512−ε≈0.41 (respectively, View the MathML source38−ε). When the triangle inequality is not assumed on any objective function, the algorithm is View the MathML source1+2214−ε≈0.27-approximate.
Subjects / Keywords
Max TSP