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

DOI10.1137/S0895480194278246zbMATH Open0874.68228OpenAlexW2036001116MaRDI QIDQ4337735FDOQ4337735

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

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

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)

Cited In (10)

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

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)