EUVIMEDEUVIMED entdecken
Open Access · CC BY-NC-SA 4.0

Approximation result toward nearest neighbor heuristic

Jér"me Monnot

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).

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →