Not all insertion methods yield constant approximate tours in the Euclidean plane

DOI10.1016/0304-3975(94)90257-7MaRDI QIDQ1318697zbMATHOpenAlexFDO

Authors Vineet Bafna, Bala Kalyanasundaram, Kirk Pruhs

Publication date 5 April 1994

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0304-3975(94)90257-7

zbMATH Keywords

traveling salesmaninsertion heuristicconstant-factor approximation algorithm

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Recommendations

• Lower Bounds for Insertion Methods for TSP
• Touring polygons: an approximation algorithm
• Existence and computation of tours through imprecise points
• On the complexity of approximating Euclidean traveling salesman tours and minimum spanning trees
• scientific article; zbMATH DE number 1559543
• Euclidean Traveling Salesman Tours through Stochastic Neighborhoods
• Efficient algorithms for touring a sequence of convex polygons and related problems
• Approximation algorithms for geometrical distance problems that are not solvable exactly
• Worst Case Length of Nearest Neighbor Tours for the Euclidean Traveling Salesman Problem
• On constant-weight TSP-tours

Cites work

• scientific article; zbMATH DE number 432754 (Why is no real title available?)
• scientific article; zbMATH DE number 3898613 (Why is no real title available?)
• scientific article; zbMATH DE number 4062645 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• An Analysis of Several Heuristics for the Traveling Salesman Problem
• Constructing Reliable Communication Networks of Small Weight Online
• Constructing competitive tours from local information
• Dynamic Steiner Tree Problem
• Lower Bounds for Insertion Methods for TSP
• The relative neighbourhood graph of a finite planar set

Cited in

(8)

• Lower Bounds for Insertion Methods for TSP
• Introducing complexity curtailing techniques for the tour construction heuristics for the travelling salesperson problem
• Insertion heuristics for central cycle problems
• The power of recourse for online MST and TSP
• Distributed boundary coverage with a team of networked miniature robots using a robust market-based algorithm
• Constructing competitive tours from local information
• Probabilistic analysis of optimization problems on sparse random shortest path metrics
• Constructing competitive tours from local information

This page was built for publication: Not all insertion methods yield constant approximate tours in the Euclidean plane

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