| Autor: |
Hougardy, Stefan, Zhong, Xianghui |
| Zdroj: |
Mathematical Programming Computation; Mar2021, Vol. 13 Issue 1, p51-74, 24p |
| Abstrakt: |
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 Concorde, the fastest existing exact TSP solver. For a 200 vertex instance from our family of Euclidean Traveling Salesman instances Concorde 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. [ABSTRACT FROM AUTHOR] |
| Databáze: |
Complementary Index |
| Externí odkaz: |
|
Full text from SpringerLink