The Traveling Salesman ProblemE.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan, D.B. Shmoys 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
Motivation and modeling | 18 |
GENERALIZATIONS OF THE TSP AND RELATED PROBLEMS | 25 |
VARIANTS OF THE TSP | 31 |
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 D.B. Shmoys,J.K. Lenstra,A.H.G. Rinnooy Kan,E.L. Lawler 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 arcs assignment problem bounding procedure branch and bound c₁ CCAO Chapter Christofides cities coefficients columns 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 objective function obtained optimal assignment optimal solution optimal tour Padberg Papadimitriou polynomial polytope proof Prove relaxation respect route satisfies Section shortest shown in Figure solved Step subgraph subproblem subset subtour elimination constraints Suppose symmetric TSP Theorem transformation traveling salesman problem triangle inequality v₁ variables vertices
Odniesienia do tej książki
Diagraphs: Theory, Algorithms and Applications Jørgen Bang-Jensen,Gregory Gutin Ograniczony podgląd - 2002 |
Evolutionary Economics: Post-Schumpeterian Contributions Esben Sloth Andersen Ograniczony podgląd - 1996 |