The traveling salesman problem : a computational study / David L. Applegate ... [and others].

Format:

Book

Contributor:

Applegate, David L.

Harry E. Humphreys Book Fund.

Series:

Princeton series in applied mathematics

Language:

English

Subjects (All):

Traveling salesman problem.

Physical Description:

ix, 593 pages : illustrations, maps ; 24 cm.

Place of Publication:

Princeton : Princeton University Press, [2006]

Summary:

"This book addresses one of the most famous and important combinatorial-optimization problems--the traveling salesman problem. It is very well written, with a vivid style that captures the reader's attention. Many examples are provided that are very useful to motivate and help the reader to better understand the results presented in the book."--Matteo Fischetti, University of Padova

"This is a fantastic book. Ever since the early days of discrete optimization, the traveling salesman problem has served as the model for computationally hard problems. The authors are main players in this area who forged a team in 1988 to push the frontiers on how good we are in solving hard and large traveling salesman problems. Now they lay out their views, experience, and findings in this book."--Bert Gerards, Centrum voor Wiskunde en Informatica

Contents:

The problem

Applications

Dantzig, Fulkerson, and Johnson

History of TSP computation

LP bounds and cutting planes

Subtour cuts and PQ-trees

Cuts from blossoms and blocks

Combs from consecutive ones

Combs from dominoes

Cut metamorphoses

Local cuts

Managing the linear programming problems

The linear programming solver

Branching

Tour finding

Computation

The road goes on.

Notes:

Includes bibliographical references (pages [541]-581) and index.

Local Notes:

Acquired for the Penn Libraries with assistance from the Harry E. Humphreys Book Fund.

ISBN:

0691129932

9780691129938

OCLC:

83853510