On the nearest neighbor rule for the traveling salesman problem

DOI10.1016/S0167-6377(03)00093-2zbMath1056.90117OpenAlexW2101753085MaRDI QIDQ1433650

Gerhard J. Woeginger, Cor A. J. Hurkens

Publication date: 1 July 2004

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

Full work available at URL: https://doi.org/10.1016/s0167-6377(03)00093-2

zbMATH Keywords

Traveling salesman problemLower boundHeuristic

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Related Items (13)

An improved lower bound for competitive graph exploration ⋮ THE NEAREST UNVISITED VERTEX WALK ON RANDOM GRAPHS ⋮ Lower and upper competitive bounds for online directed graph exploration ⋮ Online graph exploration on trees, unicyclic graphs and cactus graphs ⋮ A hybrid scatter search for the probabilistic traveling salesman problem ⋮ Online graph exploration: New results on old and new algorithms ⋮ Truly tight bounds for TSP heuristics ⋮ Exploring Endless Space ⋮ Diversified local search strategy under scatter search framework for the probabilistic traveling salesman problem ⋮ On the nearest neighbor rule for the metric traveling salesman problem ⋮ Online Graph Exploration: New Results on Old and New Algorithms ⋮ The approximation ratio of the greedy algorithm for the metric traveling salesman problem ⋮ Solving the Watchman Route Problem with Heuristic Search

Cites Work

• Efficient special case algorithms for the n-line planar traveling salesman problem
• An Analysis of Several Heuristics for the Traveling Salesman Problem
• Unnamed Item

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