Lower Bounds for Insertion Methods for TSP

DOI10.1017/S096354830000119XzbMath0811.90106MaRDI QIDQ4314147

Yossi Azar

Publication date: 1 May 1995

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

zbMATH Keywords

traveling salesmanrandom insertion method

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60)

Related Items

Constructing competitive tours from local information, Truly tight bounds for TSP heuristics, Random shortest paths: non-Euclidean instances for metric optimization problems, IntraClusTSP -- an incremental intra-cluster refinement heuristic algorithm for symmetric travelling salesman problem, Not all insertion methods yield constant approximate tours in the Euclidean plane

Cites Work

• Unnamed Item
• Unnamed Item
• On-line Steiner trees in the Euclidean plane
• A geometric problem involving the nearest neighbour algorithm
• A problem seminar
• A travelling salesman problem in the \(k\)-dimensional unit cube
• Approximate Traveling Salesman Algorithms
• Dynamic Steiner Tree Problem
• An Analysis of Several Heuristics for the Traveling Salesman Problem