Approximation results toward nearest neighbor heuristic

dc.contributor.author	Monnot, Jérôme HAL ID: 178759 ORCID: 0000-0002-7452-6553
dc.date.accessioned	2010-04-12T07:53:43Z
dc.date.available	2010-04-12T07:53:43Z
dc.date.issued	2002
dc.identifier.uri	https://basepub.dauphine.fr/handle/123456789/3913
dc.language.iso	en	en
dc.subject	Traveling salesman problem	en
dc.subject	Analysis of algorithms	en
dc.subject	performance ratio	en
dc.subject	Approximate algorithms	en
dc.subject.ddc	003	en
dc.title	Approximation results toward nearest neighbor heuristic	en
dc.type	Article accepté pour publication ou publié
dc.description.abstracten	In 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.isversionofjnlname	Yugoslav Journal of Operations Research
dc.relation.isversionofjnlvol	12	en
dc.relation.isversionofjnlissue	1	en
dc.relation.isversionofjnldate	2002
dc.relation.isversionofjnlpages	11-16	en
dc.relation.isversionofdoi	http://dx.doi.org/10.2298/YJOR0201011M	en
dc.description.sponsorshipprivate	oui	en
dc.subject.ddclabel	Recherche opérationnelle	en

Related items