Afficher la notice abrégée

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


Fichiers attachés à cette notice

FichiersTailleFormatConsulter

Il n'y a pas de fichiers associés à cette notice.

Ce document fait partie de la (des) collection(s) suivante(s)

Afficher la notice abrégée