Worst Case Length of Nearest Neighbor Tours for the Euclidean Traveling Salesman Problem

DOI10.1137/S0895480194278246MaRDI QIDQ4337735zbMATHOpenAlexFDO

Authors Leandros Tassiulas

Publication date 26 May 1997

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s0895480194278246

zbMATH Keywords

worst case analysisEuclidean traveling salesman problemnearest neighbor tours

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27)

Recommendations

• On the nearest neighbor rule for the metric traveling salesman problem
• How Long Can a Euclidean Traveling Salesman Tour Be?
• A Priori Bounds on the Euclidean Traveling Salesman
• scientific article; zbMATH DE number 437572

Cited in

(11)

• On the nearest neighbor rule for the metric traveling salesman problem
• A geometric problem involving the nearest neighbour algorithm
• scientific article; zbMATH DE number 437572 (Why is no real title available?)
• Finite Size and Dimensional Dependence in the Euclidean Traveling Salesman Problem
• Not all insertion methods yield constant approximate tours in the Euclidean plane
• On the nearest neighbor rule for the traveling salesman problem
• Euclidean Traveling Salesman Tours through Stochastic Neighborhoods
• Quantizers ad the worst case Euclidean traveling salesman problem
• Degree bounded bottleneck spanning trees in three dimensions
• scientific article; zbMATH DE number 4199979 (Why is no real title available?)
• On the probability distribution of the local times of diagonally operator-self-similar Gaussian fields with stationary increments

This page was built for publication: Worst Case Length of Nearest Neighbor Tours for the Euclidean Traveling Salesman Problem

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