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

DOI10.1016/0304-3975(94)90257-7zbMath0802.90108OpenAlexW2041332016MaRDI QIDQ1318697

Bala Kalyanasundaram, Vineet Bafna, Kirk R. 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)

Related Items (5)

Constructing competitive tours from local information ⋮ Constructing competitive tours from local information ⋮ Probabilistic analysis of optimization problems on sparse random shortest path metrics ⋮ 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

Cites Work

• The relative neighbourhood graph of a finite planar set
• Dynamic Steiner Tree Problem
• An Analysis of Several Heuristics for the Traveling Salesman Problem
• Lower Bounds for Insertion Methods for TSP
• Constructing Reliable Communication Networks of Small Weight Online
• Constructing competitive tours from local information
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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