Show simple item record

dc.contributor.authorCalvo, Roberto Wolfler
dc.contributor.authorPaschos, Vangelis
dc.contributor.authorDella Croce, Federico
dc.date.accessioned2010-04-09T14:39:17Z
dc.date.available2010-04-09T14:39:17Z
dc.date.issued2010
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/3909
dc.language.isoenen
dc.subjectApproximationen
dc.subject2-peripatetic salesman problemen
dc.subject.ddc003en
dc.titleApproximating the Metric 2-Peripatetic Salesman Problemen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenThis paper deals with the 2-Peripatetic Salesman Problem for the case where costs respect the triangle inequality. The aim is to determine 2 edge disjoint Hamiltonian cycles of minimum total cost on a graph. We first present a straightforward 9/4 approximation algorithm based on the well known Christofides algorithm for the travelling salesman problem. Then we propose a 2(n-1)/n-approximation polynomial time algorithm based on the solution of the minimum cost two-edge-disjoint spanning trees problem. Finally, we show that by partially combining these two algorithms, a 15/8 approximation ratio can be reached if a 5/4 approximation algorithm can be found for the related problem of finding two edge disjoint subgraphs consisting in a spanning tree and an hamiltonian cycle of minimum total cost.en
dc.relation.isversionofjnlnameAlgorithmic Operations Research
dc.relation.isversionofjnlvol5
dc.relation.isversionofjnlissue1
dc.relation.isversionofjnldate2010
dc.relation.isversionofjnlpages13-20
dc.description.sponsorshipprivateouien
dc.relation.isversionofjnlpublisherPreeminent Academic Facets Inc.en
dc.subject.ddclabelRecherche opérationnelleen


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record