Show simple item record

dc.contributor.authorMonnot, Jérôme
HAL ID: 178759
ORCID: 0000-0002-7452-6553
dc.date.accessioned2010-04-12T07:53:43Z
dc.date.available2010-04-12T07:53:43Z
dc.date.issued2002
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/3913
dc.language.isoenen
dc.subjectTraveling salesman problemen
dc.subjectAnalysis of algorithmsen
dc.subjectperformance ratioen
dc.subjectApproximate algorithmsen
dc.subject.ddc003en
dc.titleApproximation results toward nearest neighbor heuristicen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenIn this paper, we revisit the famous heuristic called nearest neighbor (NN) for the traveling salesman problem under maximization and minimization goal. We deal with variants where the edge costs belong to interval [a; ta] for a > 0 and t > 1, which certainly corresponds to practical cases of these problems. We prove that NN is a (t + 1)/2t-approximation for Max TSP[a; ta] and a 2/(t + 1)-approximation for Min TSP[a; ta] under the standard performance ratio. Moreover, we show that these ratios are tight for some instances.en
dc.relation.isversionofjnlnameYugoslav Journal of Operations Research
dc.relation.isversionofjnlvol12en
dc.relation.isversionofjnlissue1en
dc.relation.isversionofjnldate2002
dc.relation.isversionofjnlpages11-16en
dc.relation.isversionofdoihttp://dx.doi.org/10.2298/YJOR0201011Men
dc.description.sponsorshipprivateouien
dc.subject.ddclabelRecherche opérationnelleen


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record