Implementation and Numerical Evaluation of Traub and Vygen Algorithm for the Subtour Cover Problem
摘要
The Subtour Cover Problem (SCP) is an important building block of the state-of-the-art approximation constant-ratio approximation algorithms for the classic Asymmetric Traveling Salesman Problem (ATSP). In particular, the best-known \((17+\varepsilon )\) -approximation algorithm for the ATSP proposed by Traub and Vygen significantly relies on (2, 2, 1)-algorithm for the SCP. Despite the importance of this breakthrough approach in the field of polynomial-time approximation of the ATSP within constant ratios, without numerical implementation, its argument still remains mostly theoretical one and non-perfectly constructive. This makes it difficult to evaluate tightness of the obtained performance guarantees and employ the entire approximation framework in practice. In this paper, we propose the first implementation of (2, 2, 1)-algorithm and report results of numerical evaluation of its performance obtained on instances originating from the well-known DIMACS benchmarking library.