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

DOI10.1080/02331938608843104zbMath0596.90096OpenAlexW1981747540MaRDI 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 salesmanpatchingapproximate solutionworst case analysis

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Extremal problems in graph theory (05C35) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08)

Related Items (1)

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

This page was built for publication: Sharp bounds for Karp's “patching”-algorithm for the approximate solution of the traveling salesman problem