The Traveling Salesman ProblemE.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan, D.B. Shmoys The Traveling Salesman Problem is central to the area of Combinatorial Optimization, and it is through this problem that many of the most important developments in the area have been made. This book focuses on essential ideas; through them it illustrates all the concepts and techniques of combinatorial optimization concisely but comprehensively. The extensive reference list and numerous exercises direct the reader towards related fields, and give results. Each of the twelve chapters in this volume is concerned with a specific aspect of the Traveling Salesman Problem, and is written by an authority on that aspect. It is hoped, that the book will serve as a state-of-the-art survey of the Traveling Salesman problem which will encourage further investigations, and that it will also be useful for its comprehensive coverage of the techniques of combinatorial optimization. |
Contents
Motivation and modeling | 18 |
VARIANTS OF THE | 31 |
Computational complexity | 37 |
Copyright | |
14 other sections not shown
Other editions - View all
The Traveling Salesman Problem E.L. Lawler,J.K. Lenstra,A.H.G. Rinnooy Kan,D.B. Shmoys Snippet view - 1985 |
The Traveling Salesman Problem D.B. Shmoys,J.K. Lenstra,A.H.G. Rinnooy Kan,E.L. Lawler Snippet view - 1985 |
The Traveling Salesman Problem E.L. Lawler,J.K. Lenstra,A.H.G. Rinnooy Kan,D.B. Shmoys Snippet view - 1985 |
Common terms and phrases
2-matching constraints arcs assignment problem bottleneck bounding procedure branch and bound c₁ CCAO Chapter Christofides cities comb combinatorial optimization combinatorial optimization problems complete complete graph computational construction contains convex hull corresponding cost cut-set cutting plane decision problem defines a facet denote digraph distance matrix edges endpoint equations Euclidean TSP Eulerian Exercise exists exponential facet identification facet-defining facet-inducing facets of Q given graph G grid graph Grötschel Hamiltonian cycle Hamiltonian path heuristic incidence vectors instance INTEGER PROGRAMMING Lemma linear programming lower bound matroid method minimize minimum spanning tree node non-Hamiltonian NP-complete NP-hard objective function obtained optimal assignment optimal solution optimal tour Padberg Papadimitriou polynomial polytope proof Prove relaxation route S₁ satisfies Section shortest shown in Figure solved Step subgraph subproblem subset subtour elimination constraints symmetric TSP Theorem transformation traveling salesman traveling salesman problem triangle inequality v₁ variables vertices