The Design of Approximation Algorithms

by David P. Williamson , David B. Shmoys

• ISBN13: 9780521195270
• ISBN10: 0521195276
• eBook ISBN(s): 9781139065153
• Format: Hardcover
• Copyright: 2011-04-26
• Publisher: Cambridge University Press
• More Book Details

Summary

Discrete optimization problems are everywhere, from traditional operations research planning problems, such as scheduling, facility location, and network design; to computer science problems in databases; to advertising issues in viral marketing. Yet most such problems are NP-hard. Thus unless P = NP, there are no efficient algorithms to find optimal solutions to such problems. This book shows how to design approximation algorithms: efficient algorithms that find provably near-optimal solutions. The book is organized around central algorithmic techniques for designing approximation algorithms, including greedy and local search algorithms, dynamic programming, linear and semidefinite programming, and randomization. Each chapter in the first part of the book is devoted to a single algorithmic technique, which is then applied to several different problems. The second part revisits the techniques but offers more sophisticated treatments of them. The book also covers methods for proving that optimization problems are hard to approximate. Designed as a textbook for graduate-level algorithms courses, the book will also serve as a reference for researchers interested in the heuristic solution of discrete optimization problems.

Table of Contents

Preface	p. ix
An Introduction to the Techniques
An Introduction to Approximation Algorithms	p. 3
The Whats and Whys of Approximation Algorithms	p. 3
An Introduction to the Techniques and to Linear Programming: The Set Cover Problem	p. 6
A Deterministic Rounding Algorithm	p. 9
Rounding a Dual Solution	p. 10
Constructing a Dual Solution: The Primal-Dual Method	p. 14
A Randomized Rounding Algorithm	p. 19
Exercises	p. 22
Chapter Notes	p. 24
Greedy Algorithms and Local Search	p. 27
Scheduling Jobs with Deadlines on a Single Machine	p. 28
The k-Center Problem	p. 30
Scheduling Jobs on Identical Parallel Machines	p. 32
The Traveling Salesman Problem	p. 35
Maximizing Float in Bank Accounts	p. 40
Finding Minimum-Degree Spanning Trees	p. 43
Edge Coloring	p. 47
Exercises	p. 51
Chapter Notes	p. 54
Rounding Data and Dynamic Programming	p. 57
The Knapsack Problem	p. 57
Scheduling Jobs on Identical Parallel Machines	p. 61
The Bin-Packing Problem	p. 66
Exercises	p. 70
Chapter Notes	p. 71
Deterministic Rounding of Linear Programs	p. 73
Minimizing the Sum of Completion Times on a Single Machine	p. 74
Minimizing the Weighted Sum of Completion Times on a Single Machine	p. 76
Solving Large Linear Programs in Polynomial Time via the Ellipsoid Method	p. 79
The Prize-Collecting Steiner Tree Problem	p. 80
The Uncapacitated Facility Location Problem	p. 83
The Bin-Packing Problem	p. 88
Exercises	p. 93
Chapter Notes	p. 96
Random Sampling and Randomized Rounding of Linear Programs	p. 99
Simple Algorithms for MAX SAT and MAX CUT	p. 100
Derandomization	p. 103
Flipping Biased Coins	p. 104
Randomized Rounding	p. 106
Choosing the Better of Two Solutions	p. 109
Nonlinear Randomized Rounding	p. 111
The Prize-Collecting Steiner Tree Problem	p. 113
The Uncapacitated Facility Location Problem	p. 116
Scheduling a Single Machine with Release Dates	p. 119
Chernoff Bounds	p. 124
Integer Multicommodity Flows	p. 128
Random Sampling and Coloring Dense 3-Colorable Graphs	p. 130
Exercises	p. 132
Chapter Notes	p. 135
Randomized Rounding of Semidefinite Programs	p. 137
A Brief Introduction to Semidefinite Programming	p. 137
Finding Large Cuts	p. 139
Approximating Quadratic Programs	p. 143
Finding a Correlation Clustering	p. 146
Coloring 3-Colorable Graphs	p. 149
Exercises	p. 152
Chapter Notes	p. 155
The Primal-Dual Method	p. 157
The Set Cover Problem: A Review	p. 157
Choosing Variables to Increase: The Feedback Vertex Set Problem in Undirected Graphs	p. 160
Cleaning Up the Primal Solution: The Shortest s-t Path Problem	p. 164
Increasing Multiple Variables at Once: The Generalized Steiner Tree Problem	p. 167
Strengthening Inequalities: The Minimum Knapsack Problem	p. 174
The Uncapacitated Facility Location Problem	p. 177
Lagrangean Relaxation and the k-Median Problem	p. 182
Exercises	p. 188
Chapter Notes	p. 191
Cuts and Metrics	p. 193
The Multiway Cut Problem and a Minimum-Cut-Based Algorithm	p. 194
The Multiway Cut Problem and an LP Rounding Algorithm	p. 195
The Multicut Problem	p. 201
Balanced Cuts	p. 206
Probabilistic Approximation of Metrics by Tree Metrics	p. 210
An Application of Tree Metrics: Buy-at-Bulk Network Design	p. 215
Spreading Metrics, Tree Metrics, and Linear Arrangement	p. 218
Exercises	p. 224
Chapter Notes	p. 227
Further Uses of the Techniques
Further Uses of Greedy and Local Search Algorithms	p. 231
A Local Search Algorithm for the Uncapacitated Facility Location Problem	p. 232
A Local Search Algorithm for the k-Median Problem	p. 238
Minimum-Degree Spanning Trees	p. 242
A Greedy Algorithm for the Uncapacitated Facility Location Problem	p. 246
Exercises	p. 251
Chapter Notes	p. 253
Further Uses of Rounding Data and Dynamic Programming	p. 255
The Euclidean Traveling Salesman Problem	p. 256
The Maximum Independent Set Problem in Planar Graphs	p. 267
Exercises	p. 275
Chapter Notes	p. 277
Further Uses of Deterministic Rounding of Linear Programs	p. 279
The Generalized Assignment Problem	p. 280
Minimum-Cost Bounded-Degree Spanning Trees	p. 284
Survivable Network Design and Iterated Rounding	p. 296
Exercises	p. 303
Chapter Notes	p. 307
Further Uses of Random Sampling and Randomized Rounding of Linear Programs	p. 309
The Uncapacitated Facility Location Problem	p. 310
The Single-Source Rent-or-Buy Problem	p. 314
The Steiner Tree Problem	p. 316
Everything at Once: Finding a Large Cut in a Dense Graph	p. 324
Exercises	p. 329
Chapter Notes	p. 331
Further Uses of Randomized Rounding of Semidefinite Programs	p. 333
Approximating Quadratic Programs	p. 334
Coloring 3-Colorable Graphs	p. 341
Unique Games	p. 345
Exercises	p. 352
Chapter Notes	p. 354
Further Uses of the Primal-Dual Method	p. 355
The Prize-Collecting Steiner Tree Problem	p. 355
The Feedback Vertex Set Problem in Undirected Graphs	p. 360
Exercises	p. 366
Chapter Notes	p. 368
Further Uses of Cuts and Metrics	p. 369
Low-Distortion Embeddings and the Sparsest Cut Problem	p. 370
Oblivious Routing and Cut-Tree Packings	p. 377
Cut-Tree Packings and the Minimum Bisection Problem	p. 383
The Uniform Sparsest Cut Problem	p. 387
Exercises	p. 406
Chapter Notes	p. 408
Techniques in Proving the Hardness of Approximation	p. 409
Reductions from NP-Complete Problems	p. 410
Reductions that Preserve Approximation	p. 414
Reductions from Probabilistically Checkable Proofs	p. 424
Reductions from Label Cover	p. 429
Reductions from Unique Games	p. 442
Chapter Notes	p. 450
Open Problems	p. 453
Linear Programming	p. 459
NP-Completeness	p. 465
Bibliography	p. 469
Author Index	p. 485
Subject Index	p. 491
Table of Contents provided by Ingram. All Rights Reserved.