Sharp bounds for Karp's “patching”-algorithm for the approximate solution of the traveling salesman problem

DOI10.1080/02331938608843104zbMath0596.90096MaRDI QIDQ3730367

Bernd Jeromin, Frank Koerner

Publication date: 1986

Published in: Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1080/02331938608843104

zbMATH Keywords

traveling salesman; patching; approximate solution; worst case analysis

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

05C35: Extremal problems in graph theory

90C08: Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.)

Related Items

Triangle inequality and symmetry in connection with the assignment and the traveling salesman problem

Cites Work

• Probabilistic analysis of combinatorial algorithms: A bibliography with selected annotations
• Identification of non-optimal arcs for the traveling salesman problem
• On the refinement of bounds of heuristic algorithms for the traveling salesman problem
• A Patching Algorithm for the Nonsymmetric Traveling-Salesman Problem
• Technical Note—Data-Dependent Bounds for Heuristics to Find a Minimum Weight Hamiltonian Circuit
• On the worst-case performance of some algorithms for the asymmetric traveling salesman problem
• P-Complete Approximation Problems
• An Analysis of Several Heuristics for the Traveling Salesman Problem
• Travelling Salesman and Assignment Problems: A Survey
• Zu verschärfungen der christofibes-schranke fü den wert einer optimalen tour des enndrelseproblems