Data di Pubblicazione:
2004
Citazione:
A note on the approximation of the Asymmetric Traveling Salesman Problem / G. Righini, M. Trubian. - In: EUROPEAN JOURNAL OF OPERATIONAL RESEARCH. - ISSN 0377-2217. - 153:1(2004), pp. 255-265. [10.1016/S0377-2217(02)00794-4]
Abstract:
We show that some asymmetric traveling salesman problem (ATSP) instances are approximable within bounds equal to 3 and 9/5, when they satisfy sufficient conditions more restrictive than the triangle inequality, very simple to test and nicely structured: they only depend on a measure of satisfaction of the triangle inequality and a measure of the graph asymmetry. We discuss the applicability of such conditions and we present two preprocessing linear programs to reformulate ATSP instances into equivalent ones achieving data-dependent bounds by the same approximation algorithms.
Tipologia IRIS:
01 - Articolo su periodico
Keywords:
Asymmetric traveling salesman problem ; Worst-case approximation bounds
Elenco autori:
G. Righini, M. Trubian
Link alla scheda completa: