Structural Properties of Hard Metric TSP Inputs

DOI10.1007/978-3-642-18381-2_33zbMath1298.90089OpenAlexW1513989689MaRDI QIDQ3075532

Tobias Mömke

Publication date: 15 February 2011

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

Full work available at URL: https://doi.org/10.1007/978-3-642-18381-2_33

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (1)

On the Approximation Ratio of the Path Matching Christofides Algorithm

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Analysis of Christofides' heuristic: some paths are more difficult than cycles
• Approximation algorithms with bounded performance guarantees for the clustered traveling salesman problem
• Towards the notion of stability of approximation for hard optimization tasks and the traveling salesman problem.
• Reoptimization of the metric deadline TSP
• On the approximability of the traveling salesman problem
• Improved Approximations for TSP with Simple Precedence Constraints
• Confronting hardness using a hybrid approach
• P-Complete Approximation Problems
• Reoptimizing the traveling salesman problem
• On the Hardness of Reoptimization
• Reoptimization of Minimum and Maximum Traveling Salesman’s Tours
• Algorithms and Data Structures
• Graph-Theoretic Concepts in Computer Science

This page was built for publication: Structural Properties of Hard Metric TSP Inputs