On the nearest neighbor rule for the Traveling Salesman Problem

Cor A.J. Hurkens; Gerhard Woeginger

doi:10.1016/S0167-6377(03)00093-2

On the nearest neighbor rule for the Traveling Salesman Problem

Cor A.J. Hurkens, Gerhard Woeginger

Discrete Mathematics and Mathematical Programming

Research output: Contribution to journal › Article › Academic › peer-review

45 Citations (Scopus)

76 Downloads (Pure)

Abstract

Rosenkrantz et al. (SIAM J. Comput. 6 (1977) 563) and Johnson and Papadimitriou (in: E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan, D.B. Shmoys (Eds.), The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, Wiley, Chichester, 1985, pp. 145–180, (Chapter 5)) constructed families of TSP instances with n cities for which the nearest neighbor rule yields a tour-length that is a factor Ω(log n) above the length of the optimal tour. We describe two new families of TSP instances, for which the nearest neighbor rule shows the same bad behavior. The instances in the first family are graphical, and the instances in the second family are Euclidean. Our construction and our arguments are extremely simple and suitable for classroom use.

Original language	English
Pages (from-to)	1-4
Number of pages	4
Journal	Operations research letters
Volume	32
Issue number	1
DOIs	https://doi.org/10.1016/S0167-6377(03)00093-2
Publication status	Published - 2004

Keywords

Heuristic
Lower bound
Traveling Salesman Problem

Access to Document

10.1016/S0167-6377(03)00093-2

Cite this

@article{f236a2515afb478483618edfc2ed152b,

title = "On the nearest neighbor rule for the Traveling Salesman Problem",

abstract = "Rosenkrantz et al. (SIAM J. Comput. 6 (1977) 563) and Johnson and Papadimitriou (in: E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan, D.B. Shmoys (Eds.), The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, Wiley, Chichester, 1985, pp. 145–180, (Chapter 5)) constructed families of TSP instances with n cities for which the nearest neighbor rule yields a tour-length that is a factor Ω(log n) above the length of the optimal tour. We describe two new families of TSP instances, for which the nearest neighbor rule shows the same bad behavior. The instances in the first family are graphical, and the instances in the second family are Euclidean. Our construction and our arguments are extremely simple and suitable for classroom use.",

keywords = "Heuristic, Lower bound, Traveling Salesman Problem",

author = "Hurkens, {Cor A.J.} and Gerhard Woeginger",

year = "2004",

doi = "10.1016/S0167-6377(03)00093-2",

language = "English",

volume = "32",

pages = "1--4",

journal = "Operations research letters",

issn = "0167-6377",

publisher = "Elsevier",

number = "1",

}

TY - JOUR

T1 - On the nearest neighbor rule for the Traveling Salesman Problem

AU - Hurkens, Cor A.J.

AU - Woeginger, Gerhard

PY - 2004

Y1 - 2004

N2 - Rosenkrantz et al. (SIAM J. Comput. 6 (1977) 563) and Johnson and Papadimitriou (in: E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan, D.B. Shmoys (Eds.), The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, Wiley, Chichester, 1985, pp. 145–180, (Chapter 5)) constructed families of TSP instances with n cities for which the nearest neighbor rule yields a tour-length that is a factor Ω(log n) above the length of the optimal tour. We describe two new families of TSP instances, for which the nearest neighbor rule shows the same bad behavior. The instances in the first family are graphical, and the instances in the second family are Euclidean. Our construction and our arguments are extremely simple and suitable for classroom use.

AB - Rosenkrantz et al. (SIAM J. Comput. 6 (1977) 563) and Johnson and Papadimitriou (in: E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan, D.B. Shmoys (Eds.), The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, Wiley, Chichester, 1985, pp. 145–180, (Chapter 5)) constructed families of TSP instances with n cities for which the nearest neighbor rule yields a tour-length that is a factor Ω(log n) above the length of the optimal tour. We describe two new families of TSP instances, for which the nearest neighbor rule shows the same bad behavior. The instances in the first family are graphical, and the instances in the second family are Euclidean. Our construction and our arguments are extremely simple and suitable for classroom use.

KW - Heuristic

KW - Lower bound

KW - Traveling Salesman Problem

U2 - 10.1016/S0167-6377(03)00093-2

DO - 10.1016/S0167-6377(03)00093-2

M3 - Article

SN - 0167-6377

VL - 32

SP - 1

EP - 4

JO - Operations research letters

JF - Operations research letters

IS - 1

ER -

On the nearest neighbor rule for the Traveling Salesman Problem

Abstract

Keywords

Access to Document

Fingerprint

Cite this