On the approximation hardness of dense TSP and other path problems

DOI10.1016/S0020-0190(99)00048-4MaRDI QIDQ1606928zbMATH OpenFDO

Authors W. Fernandez de la Vega, Marek Karpinski

Publication date 25 July 2002

Published in Information Processing Letters (Search for Journal in Brave)

zbMATH Keywords

polynomial time approximation scheme

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• scientific article; zbMATH DE number 2119646
• scientific article; zbMATH DE number 1839451
• Differential approximation results for the traveling salesman problem with distances 1 and 2
• scientific article; zbMATH DE number 1754594
• On the Approximation Hardness of Some Generalizations of TSP

Cited in

(8)

• Hardness of Approximation Results for the Problem of Finding the Stopping Distance in Tanner Graphs
• A polynomial-time algorithm to determine (almost) Hamiltonicity of dense regular graphs
• scientific article; zbMATH DE number 2119646 (Why is no real title available?)
• New approximation algorithms for \((1,2)\)-TSP
• scientific article; zbMATH DE number 1754594 (Why is no real title available?)
• Hardness of fully dense problems
• Structural properties of hard metric TSP inputs (extended abstract)
• On the \({\mathcal {H}}\)-free extension complexity of the TSP

This page was built for publication: On the approximation hardness of dense TSP and other path problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1606928)