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: 4/25/2013 | 
