Improved Approximation Lower Bounds for TSP with Distances One and Two

DOI10.4036/IIS.2002.63MaRDI QIDQ4784456zbMATH OpenOpenAlexFDO

Authors Ryo Hirade, Toshiya Itoh

Publication date 10 December 2002

Published in Interdisciplinary Information Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.4036/iis.2002.63

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• Fundamentals of Computation Theory
• An explicit lower bound for TSP with distances one and two
• A (slightly) improved approximation algorithm for metric TSP
• Improved Lower Bounds on the Approximability of the Traveling Salesman Problem
• New approximation algorithms for \((1,2)\)-TSP
• Improved lower bounds for the universal and a priori TSP
• scientific article; zbMATH DE number 1500530
• An improved approximation algorithm for TSP in the half integral case
• Algorithms – ESA 2005
• An improved approximation algorithm for the maximum TSP

Cited in

(5)

• Differential approximation results for the traveling salesman problem with distances 1 and 2
• Fundamentals of Computation Theory
• An explicit lower bound for TSP with distances one and two
• Improved Lower Bounds on the Approximability of the Traveling Salesman Problem
• A (slightly) improved approximation algorithm for metric TSP

This page was built for publication: Improved Approximation Lower Bounds for TSP with Distances One and Two

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