**Introduction**

0.1 What can approximation algorithms do for you: an illustrative example

0.2 Fundamentals and concepts

0.3 Objectives and organization of this book

0.4 How to use the book

0.5 Acknowledgments

**List of Contributors**

**1 Approximation Algorithms for Scheduling**

*Leslie A. Hall*

1.1 Introduction

1.2 Sequencing with release dates to minimize lateness

1.3 Identical parallel machines: beyond list scheduling

1.4 Unrelated parallel machines

1.5 Shop scheduling

1.6 Lower bounds on approximation for makespan scheduling

1.7 Min-sum objectives

1.8 Final remarks

**2 Approximation Algorithms for Bin Packing: A Survey**

*E. G. Coffman, Jr., M. R. Garey and D. S. Johnson*

2.1 Introduction

2.2 Worst-case analysis

2.3 Average-case analysis

**3 Approximation covering and packing problems: set cover, vertex cover, independent set and related problems**

*Dorit S. Hochbaum*

3.1 Introduction

3.2 The greedy algorithm for the set cover problem

3.3 The LP-algorithm for set cover

3.4 The feasible dual approach

3.5 Using other relaxation to derive dual feasible solutions

3.6 Approximating the Multicover problem

3.7 The optimal dual approach for the vertex cover and independent set problems: preprocessing

3.8 Integer programming with two variables per inequality

3.9 The maximum coverage problem and the greedy

**4 The primal-dual method for approximation algorithms and its application to the network design problems**

*Michel X. Goemans and David P. Williamson*

4.1 Introduction

4.2 The classical primal-dual method

4.3 The primal-dual method for approximation algorithms

4.4 A model of network design problems

4.5 Downwards monotone functions

4.6 0-1 proper functions

4.7 General proper functions

4.8 Extensions

4.9 Conclusions

**5 Cut problems and their application to divide-and-conquer**

*David B. Shmoys*

5.1 Introduction

5.2 Minimum multicuts and maximum multicommodity flow

5.3 Sparsest cuts and maximum concurrent flow

5.4 Minimum feedback arc sets and related problems

5.5 Finding balanced cuts and other applications

5.6 Conclusions

**6 Approximation Algorithms for Finding Highly Connected Subgraphs**

*Samir Khuller*

6.1 Introduction

6.2 Edge-Connectivity Problems

6.3 Vertex-Connectivity Problems

6.4 Strong-Connectivity Problems

6.5 Connectivity Problems

**7 Algorithms for Finding Low Degree Structures**

*Balaji Raghavachari*

7.1 Introduction

7.2 Toughness and Degree

7.3 Matchings and MDST

7.4 MDST within one of optimal

7.5 Local search techniques

7.6 Problems with edge weights - Points in Euclidean spaces

7.7 Open problems

**8 Approximation Algorithms for Geometric Problems**

*Marshall Bern and David Eppstein*

8.1 Introduction

8.2 Traveling Salesman Problem

8.3 Steiner Tree Problem

8.4 Minimum Weight Triangulation

8.5 Clustering

8.6 Separation Problems

8.7 Odds and Ends

8.8 Conclusions

**9 Various notions of approximations: Good, Better, Best and more**

*Dorit S. Hochbaum*

9.1 Introduction

9.2 Good: fixed constant approximations

9.3 Better: approximation schemes

9.4 Best: unless NP = P

9.5 Better than best

9.6 Wonderful: within one unit of optimum

**10 Hardness of Approximations**

*Sanjeev Arora and Carsten Lund*

10.1 How to prove inapproximability results

10.2 Inapproximability results for problems in class I

10.3 Inapproximability results for problems in class II

10.4 Inapproximability results for problems in class III

10.5 Inapproximability results for problems in class IV

10.6 Inapproximability results at a glance

10.7 Probabilistically checkable proofs and inapproximability

10.8 Open problems

10.9 Chapter notes

**11 Randomized Approximation Algorithms in Combinatorial Optimization**

*Rajeev Motwani, Joseph (Seffi) Naor and Prabhakar Raghavan*

11.1 Introduction

11.2 Rounding linear programs

11.3 Semidefinite programming

11.4 Concluding remarks

**12 The Markov chain Monte Carlo method: an approach to approximate counting and integration**

*Mark Jerrum and Alistair Sinclair*

12.1 Introduction

12.2 An illustrative example

12.3 Two techniques for bounding the mixing time

12.4 A more complex example: monomer-dimer systems

12.5 More applications

12.6 The Metropolis algorithm and simulated annealing

**13 On online computation**

*Sandy Irani and Anna R. Karlin*

13.1 Introduction

13.2 Three examples of competitive analysis

13.3 Theoretical underpinnings: deterministic algorithms

13.4 Theoretical underpinnings: randomized algorithms

13.5 The k-server problem revisited

13.6 Online load balancing and virtual circuit routing

13.7 Variants of competitive analysis

13.8 Conclusions

**Glossary**

**Index**