Book Search:  

 

 
Google full text of our books:

bookjacket

In Pursuit of the Traveling Salesman:
Mathematics at the Limits of Computation
William J. Cook

Book Description | Reviews
Chapter 1 [in PDF format]

TABLE OF CONTENTS:

Preface xi

Chapter 1: Challenges 1
Tour of the United States 2
An Impossible Task? 6
One Problem at a Time 10
Road Map of the Book 16

Chapter 2: Origins of the Problem 19
Before the Mathematicians 19
Euler and Hamilton 27
Vienna to Harvard to Princeton 35
And on to the RAND Corporation 38
A Statistical View 39

Chapter 3: The Salesman in Action 44
Road Trips 44
Mapping Genomes 49
Aiming Telescopes, X-rays, and Lasers 51
Guiding Industrial Machines 53
Organizing Data 56
Tests for Microprocessors 59
Scheduling Jobs 60
And More 60

Chapter 4: Searching for a Tour 62
The 48-States Problem 62
Growing Trees and Tours 65
AlterationsWhile You Wait 75
Borrowing from Physics and Biology 84
The DIMACS Challenge 91
Tour Champions 92

Chapter 5: Linear Programming 94
General-Purpose Model 94
The Simplex Algorithm 99
Two for the Price of One: LP Duality 105
The Degree LP Relaxation of the TSP 108
Eliminating Subtours 113
A Perfect Relaxation 118
Integer Programming 122
Operations Research 125

Chapter 6: Cutting Planes 127
The Cutting-Plane Method 127
A Catalog of TSP Inequalities 131
The Separation Problem 137
Edmonds’s Glimpse of Heaven 142
Cutting Planes for Integer Programming 144

Chapter 7: Branching 146
Breaking Up 146
The Search Party 148
Branch-and-bound for Integer Programming 151

Chapter 8: Big Computing 153
World Records 153
The TSP on a Grand Scale 163

Chapter 9: Complexity 168
A Model of Computation 169
The Campaign of Jack Edmonds 171
Cook’s Theorem and Karp’s List 174
State of the TSP 178
Do We Need Computers? 184

Chapter 10: The Human Touch 191
Humans versus Computers 191
Tour-finding Strategies 192
The TSP in Neuroscience 196
Animals Solving the TSP 197

Chapter 11: Aesthetics 199
Julian Lethbridge 199
Jordan Curves 201
Continuous Lines 205
Art and Mathematics 207
Chapter 12: Pushing the Limits 211

Notes 213
Bibliography 223
Index 225

Return to Book Description

File created: 11/11/2014

Questions and comments to: webmaster@press.princeton.edu
Princeton University Press

New Book E-mails
New In Print
PUP Blog
Videos/Audios
Princeton APPS
Sample Chapters
Subjects
Series
Catalogs
Princeton Legacy Library
Textbooks
Media/Reviewers
Class Use
Rights/Permissions
Ordering
Recent Awards
Princeton Shorts
Freshman Reading
PUP Europe
About Us
Contact Us
Links
F.A.Q.
MATH SITE
PUP Home


Bookmark and Share