An explicit lower bound for TSP with distances one and two

DOI10.1007/s00453-002-1001-6zbMath1045.68066OpenAlexW2914372558MaRDI QIDQ1402211

Lars Engebretsen

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

zbMATH Keywords

traveling salesman problemlower boundsapproximabilitygadget reductions

Mathematics Subject Classification ID

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