A polynomial-time solution to Papadimitriou and Steiglitz's ``traps
A polynomial-time solution to Papadimitriou and Steiglitz's ``traps''
\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.
- Solution of large-scale symmetric travelling salesman problems
- Aspects of the traveling salesman problem
- An effective implementation of the Lin-Kernighan traveling salesman heuristic
- On a linear-programming, combinatorial approach to the traveling-salesman problem
- Certification of an optimal TSP tour through 85,900 cities
- A Survey of Different Integer Programming Formulations of the Travelling Salesman Problem
- The dragon war
- Models for Solving the Travelling Salesman Problem
- On the solution of traveling salesman problems
- The symmetric travelling salesman problem. I: New fast lower bounds for the problem of optimal 2-matching
- A cutting plane algorithm for minimum perfect 2-matchings
- A Cutting Plane Algorithm for the Linear Ordering Problem
- A method for solving traveling-salesman problems
- An Effective Heuristic Algorithm for the Traveling-Salesman Problem
- Computer Solutions of the Traveling Salesman Problem
- scientific article; zbMATH DE number 3898613 (Why is no real title available?)
- scientific article; zbMATH DE number 3943559 (Why is no real title available?)
- scientific article; zbMATH DE number 4027206 (Why is no real title available?)
- scientific article; zbMATH DE number 3793772 (Why is no real title available?)
- On a linear-programming, combinatorial approach to the traveling-salesman problem
- On the symmetric travelling salesman problem: A computational study
- On the symmetric travelling salesman problem: Solution of a 120-city problem
- Optimization of a 532-city symmetric traveling salesman problem by branch and cut
- Outline of an algorithm for integer solutions to linear programs
- Solution of a Large-Scale Traveling-Salesman Problem
- Solving Large-Scale Symmetric Travelling Salesman Problems to Optimality
- Solving Large-Scale Zero-One Linear Programming Problems
- Solving Mixed Integer Programming Problems Using Automatic Reformulation
- Some Examples of Difficult Traveling Salesman Problems
This page was built for publication: A polynomial-time solution to Papadimitriou and Steiglitz's ``traps
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1109689)
