The Traveling Salesman ProblemD.B. Shmoys, J.K. Lenstra, A.H.G. Rinnooy Kan, E.L. Lawler John Wiley & Sons, Incorporated, 1985 - 473 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. |
Spis treści
E BALAS M GRÖTSCHEL | 6 |
Motivation and modeling | 17 |
Computational complexity | 37 |
Prawa autorskie | |
Nie pokazano 14 innych sekcji
Inne wydania - Wyświetl wszystko
The Traveling Salesman Problem E.L. Lawler,J.K. Lenstra,A.H.G. Rinnooy Kan,D.B. Shmoys Widok fragmentu - 1985 |
The Traveling Salesman Problem E.L. Lawler,J.K. Lenstra,A.H.G. Rinnooy Kan,D.B. Shmoys Widok fragmentu - 1985 |
The Traveling Salesman Problem E.L. Lawler,J.K. Lenstra,A.H.G. Rinnooy Kan,D.B. Shmoys Widok fragmentu - 1985 |
Kluczowe wyrazy i wyrażenia
2-matching constraints algorithm 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 defines a facet denote digraph distance matrix edges endpoint equations Euclidean TSP Exercise exists facet identification facet-defining facet-inducing facets of Q given graph G grid graph Grötschel Hamiltonian cycle Hamiltonian graphs Hamiltonian path heuristic incidence vectors instance INTEGER PROGRAMMING Karp Lemma linear programming lower bound Math matroid method minimum spanning tree node non-Hamiltonian NP-complete NP-hard objective function obtained optimal assignment optimal solution optimal tour Padberg Papadimitriou polynomial polynomial-time polytope proof Prove relaxation route satisfies Section shortest shown in Figure solve Step subgraph subproblem subset subtour elimination constraints symmetric TSP Theorem transformation traveling salesman problem triangle inequality v₁ variables vertex set vertices