On the expected efficiency of branch and bound for the asymmetric TSP

08/05/2023

∙

by   Alan Frieze, et al.

∙

0

∙

share

Let the costs C(i,j) for an instance of the asymmetric traveling salesperson problem be independent uniform [0,1] random variables. We consider the efficiency of branch and bound algorithms that use the assignment relaxation as a lower bound. We show that w.h.p. the number of steps taken in any such branch and bound algorithm is e^Ω(n^a) for some small absolute constant a>0.