Table of Contents

Back to Hochbaum main page


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.2.1 Jackson's rule
1.2.2 A simple 3/2-approximation algorithm
1.2.3 A polynomial approximation algorithm
1.2.4 Precedence constraints and preprocessing

1.3 Identical parallel machines: beyond list scheduling

1.3.1 P|r_sub j_, prec| Lmax: list scheduling revisited
1.3.2 The LPT rule for P||Cmax
1.3.3 The LPT rule for P|r_sub j_|Cmax
1.3.4 Other results for identical parallel machines

1.4 Unrelated parallel machines

1.4.1 A 2-approximation algorithm based on linear programming
1.4.2 An approximation algorithm for minimizing cost and makespan
1.4.3 A related result from network scheduling

1.5 Shop scheduling

1.5.1 A greedy 2-approximation algorithm for open shops
1.5.2 An algorithm with an absolute error bound
1.5.3 A (2 + epsilon)-approximation algorithm for fixed job and flow shops
1.5.4 The general job shop: unit-time operations

1.6 Lower bounds on approximation for makespan scheduling

1.6.1 Identical parallel machines and precedence constraints
1.6.2 Unrelated parallel machines
1.6.3 Shop scheduling

1.7 Min-sum objectives

1.7.1 Sequencing with release dates to minimize sum of completion time
1.7.2 Sequencing with precedence constraints
1.7.3 Unrelated parallel machines

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.2.1 Next Fit
2.2.2 First Fit
2.2.3 Best Fit, Worst Fit, and Almost Any Fit algorithms
2.2.4 Bounded-space online algorithms
2.2.5 Arbitrary online algorithms
2.2.6 Semi-online algorithms
2.2.7 First Fit Decreasing and Best Fit Decreasing
2.2.8 Other simple offline algorithms
2.2.9 Approximation schemes and asymptotically optimal algorithms
2.2.10 Other worst-case questions

2.3 Average-case analysis

2.3.1 Optimal packings
2.3.2 Heuristic packings
2.3.3 Discrete distributions

3 Approximation covering and packing problems: set cover, vertex cover, independent set and related problems
Dorit S. Hochbaum

3.1 Introduction

3.1.1 Definitions, formulations and applications
3.1.2 Lower bounds on approximations
3.1.3 Overview of chapter

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.7.1 The complexity of the LP-relaxation of vertex cover and independent set
3.7.2 Easily colorable graphs
3.7.3 A greedy algorithm for independent set in unweighted graphs
3.7.4 A local-ratio theorem and subgraph removal
3.7.5 Additional algorithms without preprocessing
3.7.6 Summary of approximation for vertex cover and independent set

3.8 Integer programming with two variables per inequality

3.8.1 The half integrality and the linear programming relaxation
3.8.2 Computing an approximate solution
3.8.3 The equivalence of IP2 to 2-SAT and 2-SAT to vertex cover
3.8.4 Properties of binaries integer programs
3.8.5 Dual feasible solutions for IP2

3.9 The maximum coverage problem and the greedy

3.9.1 The greedy approach
3.9.2 Applications of the maximum coverage problem

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.4.1 0-1 functions

4.5 Downwards monotone functions

4.5.1 The edge-covering problem
4.5.2 Lower-capacitated partitioning problems
4.5.3 Location-design and location-routing problems
4.5.4 Proof of Theorems 4.5 and 4.6

4.6 0-1 proper functions

4.6.1 The generalized Steiner tree problem
4.6.2 The T-join problem
4.6.3 The minimum-weight perfect matching problem
4.6.4 Point-to point connection problems
4.6.5 Exact partitioning problems

4.7 General proper functions

4.8 Extensions

4.8.1 Minimum multicut in trees
4.8.2 The prize-collecting problems
4.8.3 Vertex connectivity problems

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.2.1 Multicuts, maximum multicommodity flow, and a weak duality
5.2.2 Fractional multicuts, pipe systems, and a strong duality theorem
5.2.3 Solving the linear programs
5.2.4 Finding a good multicut

5.3 Sparsest cuts and maximum concurrent flow

5.3.1 The sparsest cut problem
5.3.2 Reducing the sparsest cut problem to the minimum multicut problem
5.3.3 Embeddings and the sparsest cut problem
5.3.4 Finding a good embedding
5.3.5 The maximum concurrent flow problem

5.4 Minimum feedback arc sets and related problems

5.4.1 An LP-based approximation algorithm
5.4.2 Analyzing the algorithm Feedback
5.4.3 Finding a good partition

5.5 Finding balanced cuts and other applications

5.5.1 Finding balanced cuts
5.5.2 Applications of balanced cut theorems

5.6 Conclusions

6 Approximation Algorithms for Finding Highly Connected Subgraphs
Samir Khuller

6.1 Introduction

6.1.1 Outline of Chapter and Techniques

6.2 Edge-Connectivity Problems

6.2.1 Weighted Edge-Connectivity
6.2.2 Unweighted Edge-Connectivity

6.3 Vertex-Connectivity Problems

6.3.1 Weighted Vertex-Connectivity
6.3.2 Unweighted Vertex-Connectivity

6.4 Strong-Connectivity Problems

6.4.1 Polynomial Time Approximation Algorithms
6.4.2 Nearly Linear-Time Implementation

6.5 Connectivity Problems

6.5.1 Increasing Edge Connectivity from 1 to 2
6.5.2 Increasing Vertex Connectivity from 1 to 2
6.5.3 Increasing Edge-Connectivity to lambda

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.4.1 Witness sets
7.4.2 The Delta* + 1 algorithm
7.4.3 Performance analysis

7.5 Local search techniques

7.5.1 MDST problem
7.5.2 Constrained forest problems
7.5.3 Performing analysis

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.1.1 Overview of Topics
8.1.2 Special Nature of Geometric Problems

8.2 Traveling Salesman Problem

8.2.1 Christofides' Algorithm
8.2.2 Heuristics
8.2.3 TSP with Neighborhoods

8.3 Steiner Tree Problem

8.3.1 Steiner Ratios
8.3.2 Better Approximations

8.4 Minimum Weight Triangulation

8.4.1 Triangulation without Steiner Points
8.4.2 Steiner Triangulation

8.5 Clustering

8.5.1 Minmax k-clustering
8.5.2 k-minimum spanning tree

8.6 Separation Problems

8.6.1 Polygon Separation
8.6.2 Polyhedron Separation
8.6.3 Point Set Separation

8.7 Odds and Ends

8.7.1 Covering Orthogonal Polygons by Rectangles
8.7.2 Packing Squares with Fixed Corners
8.7.3 Largest Congruent Subsets
8.7.4 Polygon Bisection
8.7.5 Graph Embedding
8.7.6 Low-Degree Spanning Trees
8.7.7 Shortest Paths in Space
8.7.8 Longest Subgraph Problems

8.8 Conclusions

9 Various notions of approximations: Good, Better, Best and more
Dorit S. Hochbaum

9.1 Introduction

9.1.1 Overview of chapter

9.2 Good: fixed constant approximations

9.2.1 The weighted undirected vertex feedback set problem
9.2.2 The shortest superstring problem
9.2.3 How maximization versus minimization affects approximations

9.3 Better: approximation schemes

9.3.1 A fully polynomial approximation scheme for the Knapsack problem
9.3.2 The minimum makespan and the technique of dual approximations
9.3.3 Geometric packing and covering - the shifting technique

9.4 Best: unless NP = P

9.4.1 The k-center problem
9.4.2 A powerful approximation technique for bottleneck problems
9.4.3 Best possible parallel approximation algorithms

9.5 Better than best

9.5.1 A FPAS for bin packing
9.5.2 A 9/8-approximation algorithm for edge coloring of multigraphs and beyond

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.1.1 The canonical problems
10.1.2 Inapproximability results for the canonical problems
10.1.3 Gap preserving reductions

10.2 Inapproximability results for problems in class I

10.2.1 Max-SNP

10.3 Inapproximability results for problems in class II

10.3.1 SETCOVER

10.4 Inapproximability results for problems in class III

10.4.1 LABELCOVER (maximization version)
10.4.2 LABELCOVER (min. version)
10.4.3 Nearest lattice vector problem

10.5 Inapproximability results for problems in class IV

10.5.1 CLIQUE
10.5.2 COLORING

10.6 Inapproximability results at a glance

10.6.1 How to prove other hardness results: A case study

10.7 Probabilistically checkable proofs and inapproximability

10.7.1 The PCP theorem
10.7.2 Connection to inapproximability of MAX-3SAT
10.7.3 Where the gap comes from

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.2.1 The integer multicommodity flow problem
11.2.2 Covering and packing problems
11.2.3 The maximum satisfiability problem
11.2.4 Related work

11.3 Semidefinite programming

11.3.1 The maximum cut program
11.3.2 The graph coloring problem

11.4 Concluding remarks

11.4.1 Derandomization and parallelization
11.4.2 Computational experience
11.4.3 Open problems

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.3.1 Canonical paths
12.3.2 Conductance

12.4 A more complex example: monomer-dimer systems

12.5 More applications

12.5.1 The permanent
12.5.2 Volume of convex bodies
12.5.3 Statistical physics
12.5.4 Matroid bases: an open problem

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.2.1 Paging
13.2.2 The k-server problem
13.2.3 Metrical task systems

13.3 Theoretical underpinnings: deterministic algorithms

13.3.1 Lower bounds
13.3.2 Design principles
13.3.3 Bounding competitiveness

13.4 Theoretical underpinnings: randomized algorithms

13.4.1 Example: paging
13.4.2 Lower bounds
13.4.3 The relationships between the adversaries

13.5 The k-server problem revisited

13.5.1 History
13.5.2 Notation and properties of work function
13.5.3 The work function algorithm WFA
13.5.4 Proof of (2k - 1)-competitiveness
13.5.5 The duality lemma
13.5.6 The potential function
13.5.7 Quasi-convexity and the duality lemma

13.6 Online load balancing and virtual circuit routing

13.6.1 Load balancing on unrelated machines
13.6.2 Online virtual circuit routing
13.6.3 Recent results

13.7 Variants of competitive analysis

13.8 Conclusions

Glossary

Index


Back to Hochbaum main page