Approximation Algorithms Book

1	Introduction	1
2	Set Cover	15
3	Steiner Tree and TSP	27
4	Multiway Cut and k-Cut	38
5	k-Center	47
6	Feedback Vertex Set	54
7	Shortest Superstring	61
8	Knapsack	68
9	Bin Packing	74
10	Minimum Makespan Scheduling	79
11	Euclidean TSP	84
12	Introduction to LP-Duality	93
13	Set Cover via Dual Fitting	108
14	Rounding Applied to Set Cover	119
15	Set Cover via the Primal-Dual Schema	125
16	Maximum Satisfiability	131
17	Scheduling on Unrelated Parallel Machines	140
18	Multicut and Integer Multicommodity Flow in Trees	146
19	Multiway Cut	155
20	Multicut in General Graphs	168
21	Sparsest Cut	180
22	Steiner Forest	198
23	Steiner Network	213
24	Facility Location	232
25	k-Median	243
26	Semidefinite Programming	256
27	Shortest Vector	273
28	Counting Problems	294
29	Hardness of Approximation	306
30	Open Problems	334
App. A	An Overview of Complexity Theory for the Algorithm Designer	343
App. B	Basic Facts from Probability Theory	352
	References	355
	Problem Index	371
	Subject Index	375