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.
|Titolo:||A note on the approximation of the Asymmetric Traveling Salesman Problem|
|Autori interni:||TRUBIAN, MARCO|
|Parole Chiave:||Asymmetric traveling salesman problem ; Worst-case approximation bounds|
|Settore Scientifico Disciplinare:||Settore MAT/09 - Ricerca Operativa|
|Data di pubblicazione:||2004|
|Digital Object Identifier (DOI):||10.1016/S0377-2217(02)00794-4|
|Appare nelle tipologie:||01 - Articolo su periodico|