1 October 2020 in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
12 March 2020 in Mathematical Programming Computation
The well known 4/3 conjecture states that the integrality ratio of the subtour LP is at most 4/3 for metric Traveling Salesman instances. We present a family of Euclidean Traveling Salesman instances for which we prove that the integrality ratio of the subtour LP converges to 4/3. These instances (using the rounded Euclidean norm) turn out to be hard to solve exactly with , the fastest existing exact TSP solver. For a 200 vertex instance from our family of Euclidean Traveling Salesman instances needs several days of CPU time. This is more than 1,000,000 times more runtime than for a TSPLIB instance of similar size. Thus our new family of Euclidean Traveling Salesman instances may serve as new benchmark instances for TSP algorithms.
6 May 2011 in Computational Geometry
20 July 2023 in SIAM Journal on Computing
The [Formula: see text]-Opt heuristic is a simple improvement heuristic for the traveling salesman problem. It starts with an arbitrary tour and then repeatedly replaces [Formula: see text] edges of the tour by [Formula: see text] other edges, as long as this yields a shorter tour. We will prove that for the 2-dimensional Euclidean traveling salesman problem with [Formula: see text] cities the approximation ratio of the [Formula: see text]-Opt heuristic is [Formula: see text]. This improves the upper bound of [Formula: see text] given by Chandra, Karloff, and Tovey in [ SIAM J. Comput., 28 (1999), pp. 1998–2029] and provides for the first time a nontrivial lower bound for the case [Formula: see text]. Our results not only hold for the Euclidean norm but extend to arbitrary [Formula: see text]-norms with [Formula: see text].
1 August 2002 in Information Processing Letters