The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization

by E. L. Lawler, Jan Karel Lenstra, A. H. G. Rinnooy Kan, D. B. Shmoys

Overview

Provides an in-depth treatment of the Traveling Salesman problem—the archetypical problem in combinatorial optimization. Each chapter deals with a different aspect of the problem, and has been written by an acknowledged expert in the field. Focusses on the essential ideas in a self-contained manner. Includes exercises and an extensive bibliography.

Product Details

ISBN-13:	9780471904137
Publisher:	Wiley
Publication date:	01/08/1991
Series:	Wiley Series in Discrete Mathematics & Optimization , #12
Pages:	476
Product dimensions:	6.69(w) x 9.70(h) x 1.25(d)

About the Author

Eugene Leighton Lawler was an American computer scientist, a professor of computer science at the University of California, Berkeley. Jan Karel Lenstra is the author of The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, published by Wiley.

Table of Contents

History (A. Hoffman and P. Wolfe).
Motivation and Modeling (R. Garfinkel).
Computational Complexity (D. Johnson and C. Papadimitriou).
Well-Solved Special Cases (P. Gilmore, et al.).
Performance Guarantees for Heuristics (D. Johnson and C.Papadimitriou).
Probabilistic Analysis of Heuristics (R. Karp and J. Steele).
Empirical Analysis of Heuristics (B. Golden and W. Stewart).
Polyhedral Theory (M. Grotschel and M. Padberg).
Polyhedral Algorithms (M. Padberg and M. Grotschel).
Branch and Bound Methods (E. Balas and P. Toth).
Hamiltonian Cycles (V. Chvatal).
Vehicle Routing (N. Christofides).
Bibliography.