Show simple item record

dc.contributor.authorBaburin, Aleksei
dc.contributor.authorDella Croce, Federico
dc.contributor.authorGimadi, Edward
dc.contributor.authorGlazkov, Yuri
dc.contributor.authorPaschos, Vangelis
dc.date.accessioned2010-03-15T13:48:23Z
dc.date.available2010-03-15T13:48:23Z
dc.date.issued2009
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/3691
dc.language.isoenen
dc.subjectFactoren
dc.subjectMatchingen
dc.subjectApproximationen
dc.subject2-peripatetic salesman problemen
dc.subject.ddc003en
dc.titleApproximation algorithms for the 2-peripatetic salesman problem with edge weights 1 and 2en
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenThe NP-hard problem of finding two edge-disjoint Hamiltonian cycles of minimal total weight (also known as 2- PSPmin) in a complete (undirected) graph with edge weights 1 and 2 is considered. Polynomial time approximation algorithms are proposed with performance ratios 5/4 (in the case of one weight function) and 11/7 (in the case of two weight functions), respectively.en
dc.relation.isversionofjnlnameDiscrete Applied Mathematics
dc.relation.isversionofjnlvol157en
dc.relation.isversionofjnlissue9en
dc.relation.isversionofjnldate2009-05
dc.relation.isversionofjnlpages1988-1992en
dc.relation.isversionofdoihttp://dx.doi.org/10.1016/j.dam.2008.06.025en
dc.description.sponsorshipprivateouien
dc.relation.isversionofjnlpublisherElsevieren
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