On the approximation hardness of dense TSP and other path problems
From MaRDI portal
Publication:1606928
DOI10.1016/S0020-0190(99)00048-4zbMath1002.68062MaRDI QIDQ1606928
Marek Karpinski, Wenceslas Fernandez de la Vega
Publication date: 25 July 2002
Published in: Information Processing Letters (Search for Journal in Brave)
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Related Items
A Polynomial-Time Algorithm to Determine (Almost) Hamiltonicity of Dense Regular Graphs, New Approximation Algorithms for (1,2)-TSP