On the Approximation Hardness of Some Generalizations of TSP
From MaRDI portal
Publication:5757893
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
Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)
Related Items
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