On the nearest neighbor rule for the metric traveling salesman problem

DOI10.1016/J.DAM.2014.03.012MaRDI QIDQ496440zbMATH OpenOpenAlexFDO

Authors Stefan Hougardy, Mirko Wilde

Publication date 21 September 2015

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1401.2071

zbMATH Keywords

approximation algorithmnearest neighbor ruletraveling salesman problem

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Abstract: We present a very simple family of traveling salesman instances with $n$ cities where the nearest neighbor rule may produce a tour that is $Theta(logn)$ times longer than an optimum solution. Our family works for the graphic, the euclidean, and the rectilinear traveling salesman problem at the same time. It improves the so far best known lower bound in the euclidean case and proves for the first time a lower bound in the rectilinear case.

Recommendations

• On the nearest neighbor rule for the traveling salesman problem
• 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
• scientific article; zbMATH DE number 3869068
• Approximation result toward nearest neighbor heuristic

Cites work

• An Analysis of Several Heuristics for the Traveling Salesman Problem
• scientific article; zbMATH DE number 3918121 (Why is no real title available?)
• On the nearest neighbor rule for the traveling salesman problem
• Reducibility among combinatorial problems
• The traveling-salesman problem

Cited in

(14)

• A geometric problem involving the nearest neighbour algorithm
• Traveling salesman should not be greedy: Domination analysis of greedy-type heuristics for the TSP
• On the nearest neighbor rule for the traveling salesman problem
• The approximation ratio of the greedy algorithm for the metric traveling salesman problem
• IntraClusTSP -- an incremental intra-cluster refinement heuristic algorithm for symmetric travelling salesman problem
• Worst case analysis of nearest neighbour algorithms for the minimum weighted directed k-cycle problem
• Worst Case Length of Nearest Neighbor Tours for the Euclidean Traveling Salesman Problem
• Approximation result toward nearest neighbor heuristic
• On the Metric $s$--$t$ Path Traveling Salesman Problem
• THE NEAREST UNVISITED VERTEX WALK ON RANDOM GRAPHS
• On the nearest-neighbor algorithm for the mean-field traveling salesman problem
• Truly tight bounds for TSP heuristics
• Exploring Endless Space
• The bright side of simple heuristics for the TSP

This page was built for publication: On the nearest neighbor rule for the metric traveling salesman problem

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