A geometric problem involving the nearest neighbour algorithm

DOI10.1016/0167-6377(87)90045-9MaRDI QIDQ1094335zbMATH OpenOpenAlexFDO

Authors B. George

Publication date 1987

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0167-6377(87)90045-9

zbMATH Keywords

Nearest Neighbour Algorithmtraveling salesman problem

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Programming involving graphs or networks (90C35)

Review text

It is shown that for arbitrary large n there exist sets S in the unit square of \({\mathbb{R}}^ 2\) with \(| S| \leq n\), such that starting at any chosen point \(P_ 1\in S\) and touring S according to the Nearest Neighbour Algorithm, the sum of the squares of the distances exceeds \(c\cdot \log_ 2n\), with \(c>0\).

Recommendations

• Worst Case Length of Nearest Neighbor Tours for the Euclidean Traveling Salesman Problem
• On the nearest-neighbor algorithm for the mean-field traveling salesman problem
• On the nearest neighbor rule for the metric traveling salesman problem
• scientific article; zbMATH DE number 437572
• How Long Can a Euclidean Traveling Salesman Tour Be?

Cites work

• A problem seminar
• An Analysis of Several Heuristics for the Traveling Salesman Problem
• scientific article; zbMATH DE number 4203483 (Why is no real title available?)
• The Traveling Salesman Problem: A Survey

Cited in

(3)

• A travelling salesman problem in the \(k\)-dimensional unit cube
• Lower Bounds for Insertion Methods for TSP
• On-line Steiner trees in the Euclidean plane

This page was built for publication: A geometric problem involving the nearest neighbour algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1094335)