The traveling Salesman problem: a guided tour of combinatorial optimization

John Wiley & Sons

1991

x, 465 p.

Wiley-Interscience series in discrete mathematics

Bibliography: p. 449-465.

978-0-471-90413-7

History / A.J. Hoffman, P. Wolfe -- Motivation and modeling / R.S. Garfinkel -- Computational complexity / D.S. Johnson, C.H. Papadimitriou -- Well-solved special cases / P.C. Gilmore, E.L. Lawler, D.B. Shmoys -- Performance guarantees for heuristics / D.S. Johnson, C.H. Papadimitriou -- Probabilistic analysis of heuristics / R.M. Karp, J.M. Steele -- Empirical analysis of heuristics / B.L. Golden, W.R. Stewart -- Polyhedral theory / M. Grötschel, M.W. Padberg -- Polyhedral computations / M.W. Padberg, M. Grötschel -- Branch and bound methods / E. Balas, P. Toth -- Hamiltonian cycles / V. Chvátal -- Vehicle routing / N. Christofides.

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.

Английский