On the Approximation Ratio of the Path Matching Christofides Algorithm

DOI10.1007/978-3-642-27660-6_29zbMath1302.90185OpenAlexW57550275MaRDI QIDQ2891381

Sacha Krug

Publication date: 15 June 2012

Published in: SOFSEM 2012: Theory and Practice of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-27660-6_29

zbMATH Keywords

traveling salesman problemapproximation algorithmsHamiltonian path problem

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Performance guarantees for the TSP with a parameterized triangle inequality
• Analysis of Christofides' heuristic: some paths are more difficult than cycles
• Towards the notion of stability of approximation for hard optimization tasks and the traveling salesman problem.
• On the traveling salesman problem restricted to inputs satisfying a relaxed triangle inequality
• Structural Properties of Hard Metric TSP Inputs

This page was built for publication: On the Approximation Ratio of the Path Matching Christofides Algorithm