On the Complexity of Branch and Cut Methods for the Traveling Salesman Problem

摘要

In this note, we give an extension of the results of Chvatal, Cook, and hartmann (2) on the complexity of the traveling salesman problem In particular, we shwo that the branch and cut method has an exponential worstcase running time, even if a separation oracle for the clique-tree polytope is available and the length of the optimal hamiltonian circuit is used as an upper bound.