Show simple item record

dc.contributor.authorPaschos, Vangelis
dc.contributor.authorMonnot, Jérôme
dc.contributor.authorToulouse, Sophie
dc.date.accessioned2010-01-15T15:39:10Z
dc.date.available2010-01-15T15:39:10Z
dc.date.issued2003
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/2980
dc.language.isoenen
dc.subjectApproximation algorithmsen
dc.subjectNP-complete problemen
dc.subjectTraveling salesmanen
dc.subject.ddc003en
dc.titleApproximation algorithms for the traveling salesman problemen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenWe first prove that the minimum and maximum traveling salesman problems, their metric versions as well as some versions defined on parameterized triangle inequalities (called sharpened and relaxed metric traveling salesman) are all equi-approximable under an approximation measure, called differential-approximation ratio, that measures how the value of an approximate solution is placed in the interval between the worst- and the best-value solutions of an instance. We next show that the 2OPT, one of the most-known traveling salesman algorithms, approximately solves all these problems within differential-approximation ratio bounded above by 1/2. We analyze the approximation behavior of 2OPT when used to approximately solve traveling salesman problem in bipartite graphs and prove that it achieves differential-approximation ratio bounded above by 1/2 also in this case. We also prove that, for any ε>0, it is NP-hard to differentially approximate metric traveling salesman within better than 649/650 + ε and traveling salesman with distances 1 and 2 within better than 741/742 + ε. Finally, we study the standard approximation of the maximum sharpened and relaxed metric traveling salesman problems. These are versions of maximum metric traveling salesman defined on parameterized triangle inequalities and, to our knowledge, they have not been studied until now.en
dc.relation.isversionofjnlnameMathematical Methods of Operations Research
dc.relation.isversionofjnlvol56en
dc.relation.isversionofjnlissue3en
dc.relation.isversionofjnldate2003-01
dc.relation.isversionofjnlpages387-405en
dc.relation.isversionofdoihttp://dx.doi.org/10.1007/s001860200239en
dc.description.sponsorshipprivateouien
dc.relation.isversionofjnlpublisherSpringeren
dc.subject.ddclabelRecherche opérationnelleen


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record