Show simple item record

dc.contributor.authorMonnot, Jérôme
HAL ID: 178759
ORCID: 0000-0002-7452-6553
dc.date.accessioned2010-04-13T08:12:26Z
dc.date.available2010-04-13T08:12:26Z
dc.date.issued2002
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/3945
dc.language.isoenen
dc.subjectAnalysis of algorithmsen
dc.subjectPerformance ratioen
dc.subjectDifferential ratioen
dc.subjectApproximation algorithmsen
dc.subject.ddc003en
dc.titleDifferential approximation results for the traveling salesman and related problemsen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenThis paper deals with the problem of constructing a Hamiltonian cycle of optimal weight, called TSP. We show that TSP is 2/3-differential approximable and cannot be differential approximable greater than 649/650. Next, we demonstrate that, when dealing with edge-costs 1 and 2, the same algorithm idea improves this ratio to 3/4 and we obtain a differential non-approximation threshold equal to 741/742. Remark that the 3/4-differential approximation result has been recently proved by a way more specific to the 1-, 2-case and with another algorithm in the recent conference, Symposium on Fundamentals of Computation Theory, 2001. Based upon these results, we establish new bounds for standard ratio: 5/6 for Max TSP[a,2a] and 7/8 for Max TSP[1,2]. We also derive some approximation results on partition graph problems by paths.en
dc.relation.isversionofjnlnameInformation Processing Letters
dc.relation.isversionofjnlvol82en
dc.relation.isversionofjnlissue5en
dc.relation.isversionofjnldate2002-06
dc.relation.isversionofjnlpages229-235en
dc.relation.isversionofdoihttp://dx.doi.org/10.1016/S0020-0190(01)00287-3en
dc.description.sponsorshipprivateouien
dc.relation.isversionofjnlpublisherElsevieren
dc.subject.ddclabelRecherche opérationnelleen


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record