iv CONTENTS
5.2.2 A 3-Dimensional Example . . . . . . . . . . . . . . . . . . . . . . . . 34
5.2.3 The General Case . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
5.2.4 Polynomial Time Algorithms for LInear Programming . . . . . . . . 37
5.2.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
5.3 Standard Form for Linear Programs . . . . . . . . . . . . . . . . . . . . . . 39
6 Linear Programming Duality 41
6.1 The Dual of a Linear Program . . . . . . . . . . . . . . . . . . . . . . . . . 41
7 Rounding Linear Programs 47
7.1 Linear Programming Relaxations . . . . . . . . . . . . . . . . . . . . . . . . 47
7.2 The Weighted Vertex Cover Problem . . . . . . . . . . . . . . . . . . . . . . 48
7.3 A Linear Programming Relaxation of Vertex Cover . . . . . . . . . . . . . . 50
7.4 The Dual of the LP Relaxation . . . . . . . . . . . . . . . . . . . . . . . . . 51
7.5 Linear-Time 2-Approximation of Weighted Vertex Cover . . . . . . . . . . . 52
8 Randomized Rounding 57
8.1 A Linear Programming Relaxation of Set Cover . . . . . . . . . . . . . . . . 57
8.2 The Dual of the Relaxation . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
9 Max Flow 65
9.1 Flows in Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
10 The Fattest Path 73
10.1 The “fattest” augmenting path heuristic . . . . . . . . . . . . . . . . . . . . 74
10.1.1 Dijkstra’s algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
10.1.2 Adaptation to find a fattest path . . . . . . . . . . . . . . . . . . . . 76
10.1.3 Analysis of the fattest augmenting path heuristic . . . . . . . . . . . 77
11 Strongly Polynomial Time Algorithms 79
11.1 Flow Decomposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
11.2 The Edmonds-Karp Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 81
12 The Push-Relabel Algorithm 83
12.1 The Push-Relabel Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
12.2 Analysis of the Push-Relabel Algorithm . . . . . . . . . . . . . . . . . . . . 85
评论0