The asymmetric traveling salesman path LP has constant integrality ratio

Anna Köhne, Vera Traub, Jens Vygen

We show that the classical LP relaxation of the asymmetric traveling salesman path problem (ATSPP) has constant integrality ratio. If ${\rho }_{\text{ATSP}}$ and ${\rho }_{\text{ATSPP}}$ denot…