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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Implementation and Numerical Evaluation of Traub and Vygen Algorithm for the Subtour Cover Problem

  • Ksenia Rizhenko,
  • Daniil Khachai,
  • Katherine Neznakhina,
  • Michael Khachay

摘要

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.