| |
| |
| Preface | |
| |
| |
| |
| An Introduction to the Techniques | |
| |
| |
| |
| An Introduction to Approximation Algorithms | |
| |
| |
| |
| The Whats and Whys of Approximation Algorithms | |
| |
| |
| |
| An Introduction to the Techniques and to Linear Programming: The Set Cover Problem | |
| |
| |
| |
| A Deterministic Rounding Algorithm | |
| |
| |
| |
| Rounding a Dual Solution | |
| |
| |
| |
| Constructing a Dual Solution: The Primal-Dual Method | |
| |
| |
| |
| A Randomized Rounding Algorithm | |
| |
| |
| Exercises | |
| |
| |
| Chapter Notes | |
| |
| |
| |
| Greedy Algorithms and Local Search | |
| |
| |
| |
| Scheduling Jobs with Deadlines on a Single Machine | |
| |
| |
| |
| The k-Center Problem | |
| |
| |
| |
| Scheduling Jobs on Identical Parallel Machines | |
| |
| |
| |
| The Traveling Salesman Problem | |
| |
| |
| |
| Maximizing Float in Bank Accounts | |
| |
| |
| |
| Finding Minimum-Degree Spanning Trees | |
| |
| |
| |
| Edge Coloring | |
| |
| |
| Exercises | |
| |
| |
| Chapter Notes | |
| |
| |
| |
| Rounding Data and Dynamic Programming | |
| |
| |
| |
| The Knapsack Problem | |
| |
| |
| |
| Scheduling Jobs on Identical Parallel Machines | |
| |
| |
| |
| The Bin-Packing Problem | |
| |
| |
| Exercises | |
| |
| |
| Chapter Notes | |
| |
| |
| |
| Deterministic Rounding of Linear Programs | |
| |
| |
| |
| Minimizing the Sum of Completion Times on a Single Machine | |
| |
| |
| |
| Minimizing the Weighted Sum of Completion Times on a Single Machine | |
| |
| |
| |
| Solving Large Linear Programs in Polynomial Time via the Ellipsoid Method | |
| |
| |
| |
| The Prize-Collecting Steiner Tree Problem | |
| |
| |
| |
| The Uncapacitated Facility Location Problem | |
| |
| |
| |
| The Bin-Packing Problem | |
| |
| |
| Exercises | |
| |
| |
| Chapter Notes | |
| |
| |
| |
| Random Sampling and Randomized Rounding of Linear Programs | |
| |
| |
| |
| Simple Algorithms for MAX SAT and MAX CUT | |
| |
| |
| |
| Derandomization | |
| |
| |
| |
| Flipping Biased Coins | |
| |
| |
| |
| Randomized Rounding | |
| |
| |
| |
| Choosing the Better of Two Solutions | |
| |
| |
| |
| Nonlinear Randomized Rounding | |
| |
| |
| |
| The Prize-Collecting Steiner Tree Problem | |
| |
| |
| |
| The Uncapacitated Facility Location Problem | |
| |
| |
| |
| Scheduling a Single Machine with Release Dates | |
| |
| |
| |
| Chernoff Bounds | |
| |
| |
| |
| Integer Multicommodity Flows | |
| |
| |
| |
| Random Sampling and Coloring Dense 3-Colorable Graphs | |
| |
| |
| Exercises | |
| |
| |
| Chapter Notes | |
| |
| |
| |
| Randomized Rounding of Semidefinite Programs | |
| |
| |
| |
| A Brief Introduction to Semidefinite Programming | |
| |
| |
| |
| Finding Large Cuts | |
| |
| |
| |
| Approximating Quadratic Programs | |
| |
| |
| |
| Finding a Correlation Clustering | |
| |
| |
| |
| Coloring 3-Colorable Graphs | |
| |
| |
| Exercises | |
| |
| |
| Chapter Notes | |
| |
| |
| |
| The Primal-Dual Method | |
| |
| |
| |
| The Set Cover Problem: A Review | |
| |
| |
| |
| Choosing Variables to Increase: The Feedback Vertex Set Problem in Undirected Graphs | |
| |
| |
| |
| Cleaning Up the Primal Solution: The Shortest s-t Path Problem | |
| |
| |
| |
| Increasing Multiple Variables at Once: The Generalized Steiner Tree Problem | |
| |
| |
| |
| Strengthening Inequalities: The Minimum Knapsack Problem | |
| |
| |
| |
| The Uncapacitated Facility Location Problem | |
| |
| |
| |
| Lagrangean Relaxation and the k-Median Problem | |
| |
| |
| Exercises | |
| |
| |
| Chapter Notes | |
| |
| |
| |
| Cuts and Metrics | |
| |
| |
| |
| The Multiway Cut Problem and a Minimum-Cut-Based Algorithm | |
| |
| |
| |
| The Multiway Cut Problem and an LP Rounding Algorithm | |
| |
| |
| |
| The Multicut Problem | |
| |
| |
| |
| Balanced Cuts | |
| |
| |
| |
| Probabilistic Approximation of Metrics by Tree Metrics | |
| |
| |
| |
| An Application of Tree Metrics: Buy-at-Bulk Network Design | |
| |
| |
| |
| Spreading Metrics, Tree Metrics, and Linear Arrangement | |
| |
| |
| Exercises | |
| |
| |
| Chapter Notes | |
| |
| |
| |
| Further Uses of the Techniques | |
| |
| |
| |
| Further Uses of Greedy and Local Search Algorithms | |
| |
| |
| |
| A Local Search Algorithm for the Uncapacitated Facility Location Problem | |
| |
| |
| |
| A Local Search Algorithm for the k-Median Problem | |
| |
| |
| |
| Minimum-Degree Spanning Trees | |
| |
| |
| |
| A Greedy Algorithm for the Uncapacitated Facility Location Problem | |
| |
| |
| Exercises | |
| |
| |
| Chapter Notes | |
| |
| |
| |
| Further Uses of Rounding Data and Dynamic Programming | |
| |
| |
| |
| The Euclidean Traveling Salesman Problem | |
| |
| |
| |
| The Maximum Independent Set Problem in Planar Graphs | |
| |
| |
| Exercises | |
| |
| |
| Chapter Notes | |
| |
| |
| |
| Further Uses of Deterministic Rounding of Linear Programs | |
| |
| |
| |
| The Generalized Assignment Problem | |
| |
| |
| |
| Minimum-Cost Bounded-Degree Spanning Trees | |
| |
| |
| |
| Survivable Network Design and Iterated Rounding | |
| |
| |
| Exercises | |
| |
| |
| Chapter Notes | |
| |
| |
| |
| Further Uses of Random Sampling and Randomized Rounding of Linear Programs | |
| |
| |
| |
| The Uncapacitated Facility Location Problem | |
| |
| |
| |
| The Single-Source Rent-or-Buy Problem | |
| |
| |
| |
| The Steiner Tree Problem | |
| |
| |
| |
| Everything at Once: Finding a Large Cut in a Dense Graph | |
| |
| |
| Exercises | |
| |
| |
| Chapter Notes | |
| |
| |
| |
| Further Uses of Randomized Rounding of Semidefinite Programs | |
| |
| |
| |
| Approximating Quadratic Programs | |
| |
| |
| |
| Coloring 3-Colorable Graphs | |
| |
| |
| |
| Unique Games | |
| |
| |
| Exercises | |
| |
| |
| Chapter Notes | |
| |
| |
| |
| Further Uses of the Primal-Dual Method | |
| |
| |
| |
| The Prize-Collecting Steiner Tree Problem | |
| |
| |
| |
| The Feedback Vertex Set Problem in Undirected Graphs | |
| |
| |
| Exercises | |
| |
| |
| Chapter Notes | |
| |
| |
| |
| Further Uses of Cuts and Metrics | |
| |
| |
| |
| Low-Distortion Embeddings and the Sparsest Cut Problem | |
| |
| |
| |
| Oblivious Routing and Cut-Tree Packings | |
| |
| |
| |
| Cut-Tree Packings and the Minimum Bisection Problem | |
| |
| |
| |
| The Uniform Sparsest Cut Problem | |
| |
| |
| Exercises | |
| |
| |
| Chapter Notes | |
| |
| |
| |
| Techniques in Proving the Hardness of Approximation | |
| |
| |
| |
| Reductions from NP-Complete Problems | |
| |
| |
| |
| Reductions that Preserve Approximation | |
| |
| |
| |
| Reductions from Probabilistically Checkable Proofs | |
| |
| |
| |
| Reductions from Label Cover | |
| |
| |
| |
| Reductions from Unique Games | |
| |
| |
| Chapter Notes | |
| |
| |
| |
| Open Problems | |
| |
| |
| |
| Linear Programming | |
| |
| |
| |
| NP-Completeness | |
| |
| |
| Bibliography | |
| |
| |
| Author Index | |
| |
| |
| Subject Index | |