A polynomial-time solution to Papadimitriou and Steiglitz's ``traps
From MaRDI portal
Publication:1109689
DOI10.1016/0167-6377(88)90077-6zbMath0655.90085OpenAlexW2020813360MaRDI QIDQ1109689
Ting-Yi Sung, Manfred W. Padberg
Publication date: 1988
Published in: Operations Research Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0167-6377(88)90077-6
local searchheuristiclinear programming relaxationpolynomial timetrapssubtour elimination constraintssymmetric travelling salesman
Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Linear programming (90C05) Combinatorial optimization (90C27)
Related Items (3)
A note on the traveling salesman problem ⋮ Optimal arcs for the traveling salesman problem ⋮ Special cases of the traveling salesman problem
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Optimization of a 532-city symmetric traveling salesman problem by branch and cut
- A cutting plane algorithm for minimum perfect 2-matchings
- A Cutting Plane Algorithm for the Linear Ordering Problem
- Outline of an algorithm for integer solutions to linear programs
- Solving Large-Scale Zero-One Linear Programming Problems
- On the symmetric travelling salesman problem: Solution of a 120-city problem
- On the symmetric travelling salesman problem: A computational study
- Solving Large-Scale Symmetric Travelling Salesman Problems to Optimality
- Some Examples of Difficult Traveling Salesman Problems
- Solving Mixed Integer Programming Problems Using Automatic Reformulation
- Solution of a Large-Scale Traveling-Salesman Problem
- A Method for Solving Traveling-Salesman Problems
- On a Linear-Programming, Combinatorial Approach to the Traveling-Salesman Problem
- Computer Solutions of the Traveling Salesman Problem
- An Effective Heuristic Algorithm for the Traveling-Salesman Problem
This page was built for publication: A polynomial-time solution to Papadimitriou and Steiglitz's ``traps
