An explicit lower bound for TSP with distances one and two
From MaRDI portal
Publication:1402211
DOI10.1007/s00453-002-1001-6zbMath1045.68066OpenAlexW2914372558MaRDI QIDQ1402211
Publication date: 19 August 2003
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-002-1001-6
Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
Weighted amplifiers and inapproximability results for travelling salesman problem ⋮ Lower and upper competitive bounds for online directed graph exploration ⋮ Sequentially Swapping Colored Tokens on Graphs ⋮ Towards Better Inapproximability Bounds for TSP: A Challenge of Global Dependencies ⋮ New inapproximability bounds for TSP ⋮ An approximation algorithm for the minimum co-path set problem ⋮ TSP with bounded metrics