Combinatorial Optimization: Exact and Approximate Algorithms

Foreword......Page 2
Overview......Page 7
Definitions......Page 9
The Algorithm......Page 10
Approximating the Metric Steiner Tree Problem......Page 13
Metric versus General Steiner Tree......Page 16
The Traveling Salesman Problem......Page 19
A 2-approximate Algorithm......Page 22
Eulerian Cycles......Page 24
Eulerian Cycles and TSP Approximation......Page 25
Better Approximation of the Traveling Salesman Problem......Page 27
The Set Cover Problem......Page 32
Set Cover versus Vertex Cover......Page 35
Introduction to Linear Programming......Page 37
A 2-Dimensional Example......Page 38
A 3-Dimensional Example......Page 40
The General Case......Page 42
Polynomial Time Algorithms for LInear Programming......Page 43
Summary......Page 44
Standard Form for Linear Programs......Page 45
The Dual of a Linear Program......Page 47
Linear Programming Relaxations......Page 53
The Weighted Vertex Cover Problem......Page 54
A Linear Programming Relaxation of Vertex Cover......Page 56
The Dual of the LP Relaxation......Page 57
Linear-Time 2-Approximation of Weighted Vertex Cover......Page 58
A Linear Programming Relaxation of Set Cover......Page 63
The Dual of the Relaxation......Page 68
Flows in Networks......Page 71
The Fattest Path......Page 79
The ``fattest'' augmenting path heuristic......Page 80
Dijkstra's algorithm......Page 81
Adaptation to find a fattest path......Page 82
Analysis of the fattest augmenting path heuristic......Page 83
Flow Decomposition......Page 85
The Edmonds-Karp Algorithm......Page 87
The Push-Relabel Approach......Page 89
Analysis of the Push-Relabel Algorithm......Page 91
Improved Running Time......Page 95
Global Min-Cut and Edge-Connectivity......Page 97
Reduction to Maximum Flow......Page 99
The Edge-Contraction Algorithm......Page 100
Algorithms in Bipartite Graphs......Page 105
Maximum Matching in Bipartite Graphs......Page 106
Perfect Matchings in Bipartite Graphs......Page 108
Vertex Cover in Bipartite Graphs......Page 110
The LP of Maximum Flow and Its Dual......Page 111
Generalizations of the Maximum Flow Problem......Page 119
The Sparsest Cut Problem......Page 122
Online Algorithms and Competitive Analysis......Page 127
The Secretary Problem......Page 128
Paging and Caching......Page 130
A Simplified Setting......Page 133
The General Result......Page 135
Applications......Page 138