In this presentation, I will describe a set of phase-transition
results on the asymmetric TSP (ATSP), including the phase transitions
on the computational cost of a depth-first branch-and-bound method and
the phase transtions of the backbones of the problem. I will discuss
the connection between these phase transitions and the accuracy of
distance measurement. Based on the phase-transition results, I will
present a new approximation method that exploits the phase
transitions. Experimental results will also be presented. Finally, I
will discuss the generality of these findings and describe an
application to number partitioning problem.
Copyright. All Rights Reserved.