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 |