On the Approximation Hardness of Some Generalizations of TSP

DOI10.1007/11785293_19zbMath1141.90507OpenAlexW1505235268MaRDI QIDQ5757893

Joachim Kupke, Joachim Kneis, Juraj Hromkovič, Hans-Joachim Böckenhauer

Publication date: 7 September 2007

Published in: Algorithm Theory – SWAT 2006 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/11785293_19

zbMATH Keywords

approximationinapproximabilityTSP with time windows

Mathematics Subject Classification ID

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

Related Items (7)

Improved approximations for TSP with simple precedence constraints ⋮ Stability of Reapproximation Algorithms for the $$\beta $$-Metric Traveling Salesman (Path) Problem ⋮ Reoptimization of the metric deadline TSP ⋮ Reoptimization of the Metric Deadline TSP ⋮ On the Hardness of Reoptimization ⋮ Approximation hardness of deadline-TSP reoptimization ⋮ Improved approximations for ordered TSP on near-metric graphs

This page was built for publication: On the Approximation Hardness of Some Generalizations of TSP