A polynomial-time solution to Papadimitriou and Steiglitz's ``traps'' (Q1109689)

\textit{C. H. Papadimitriou} and \textit{K. Steiglitz} [Oper. Res. 26, 434-443 (1978; Zbl 0383.90105)] constructed a class of instances called ``traps'' for the symmetric travelling salesman problem with \(n=8k\) cities. The instances in this class have exponentially many suboptimal solutions with arbitrary large weight, which are much different from the unique optimum solution, and thus the local search algorithms are ineffective to solve the class of instances. In this paper the authors show that this class of instances can be solved in polynomial time by linear programming relaxation appended with k subtour elimination constraints. Section 1 describes the class of instances given by Papadimitriou and Steiglitz, and states the properties of the instances; Section 2 gives the linear programming formulation of instances; in Section 3 the authors prove that the class of instances can be solved in polynomial time by linear programming relaxation appended with k subtour elimination constraints. Hence these instances are not traps to this algorithm based on linear programming. Finally the authors conclude that the algorithms based on linear programming for combinatorial optimization problems are substantially different from algorithms based on `local search' or `exchange' arguments.