Approximation result toward nearest neighbor heuristic
Yugoslav Journal of Operations Research · 2002
DOI: 10.2298/yjor0201011m ↗Kurz gefasst
Fachartikel in der Zeitschrift Yugoslav Journal of Operations Research, 2002. Verfasst von Jér"me Monnot. Die Arbeit wurde bisher 5-mal zitiert (Crossref) und nennt 1 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY-NC-SA 4.0).
Abstract (Originalsprache)
In this paper, we revisit the famous heuristic called nearest neighbor (N N) for the traveling salesman problem under maximization and minimization goal. We deal with variants where the edge costs belong to interval Sa;taC 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 maxTSPSa;taC and a 2/(t+1)-approximation for minTSPSa;taC under the standard performance ratio. Moreover, we show that these ratios are tight for some instances.
Zitieren
APA
Monnot, J. (2002). Approximation result toward nearest neighbor heuristic. Yugoslav Journal of Operations Research. https://doi.org/10.2298/yjor0201011m
Vancouver
Monnot J. Approximation result toward nearest neighbor heuristic. Yugoslav Journal of Operations Research. 2002. doi:10.2298/yjor0201011m
BibTeX
@article{Monnot2002,
author = {Monnot, Jér"me},
title = {Approximation result toward nearest neighbor heuristic},
journal = {Yugoslav Journal of Operations Research},
year = {2002},
doi = {10.2298/yjor0201011m}
}
EUVIMED