Preface ......................................................... 7
Aravind Srinivasan:
Approximation algorithms via randomized rounding: a survey
1 Introduction ................................................ 11
2 Preliminaries ............................................... 18
2.1. Large deviation bounds ................................. 18
3 Uniform randomized rounding ................................. 22
3.1 Simple balls-and-bins processes ........................ 22
3.2 Approximation algorithms for job-shop scheduling ....... 23
3.3 Improved dart-throwing ................................. 26
3.4 The Lovasz Local Lemma and packet-routing .............. 27
4 Analyses based on the FKG inequality ........................ 32
4.1 Lattice approximation and packing integer programs ..... 32
4.2 The FKG inequality and well-behaved estimators ......... 36
4.3 Correlations in packing and covering integer
programs ............................................... 41
4.4 Low-congestion routing and related problems ............ 43
5 Analyses via the Janson—Luczak-Ruciński inequality .......... 49
6 Applications of an extension of the Lovasz Local Lemma ...... 57
6.1 Minimax integer programs and union-bound based
analysis ............................................... 57
6.2 The extended LLL and some of its applications .......... 60
7 A very short tour of discrepancy theory ..................... 64
8 Conclusion .................................................. 66
Acknowledgements ............................................ 67
References ..................................................... 71
Nick C. Wormald:
The differential equation method for random graph processes
and greedy algorithms
1 Introduction ................................................ 75
1.1 A brief look at the general method ..................... 76
1.2 Graph processes ........................................ 77
1.3 Basic notation ......................................... 78
1.3.1 Graph Theory .................................... 78
1.3.2 Probability ..................................... 79
1.3.3 Other ........................................... 79
2 Some random processes and their histories ................... 80
3 Preliminary investigations .................................. 86
3.1 Min-degree graph process: phase 0 ...................... 86
3.2 Min-degree graph process: later phases ................. 88
3.3 Degree bounded graph process ........................... 89
3.3.1 The 2-process ................................... 90
3.3.2 The d-process for arbitrary d ................... 91
3.3.3 Probabilistic solution to the differential
equations ....................................... 92
3.3.4 Distribution of short cycles in the 2-process ... 94
3.4 Degree bounded star graph process ...................... 98
3.4.1 The star d-process in general ................... 98
3.4.2 The star 2-process .............................. 99
3.5 Simple greedy algorithm for independent sets .......... 101
4 Bounding large deviations .................................. 104
4.1 Martingales and supermartingales ...................... 105
4.2 Use of stopping times ................................. 108
4.3 Large components in d-processes ....................... 110
4.4 Bounded differences with a tail ....................... 111
5 Proving approximation by differential equations ............ 112
5.1 General-purpose theorem ............................... 113
5.2 The wholistic approach ................................ 118
5.3 Simple applications ................................... 120
5.4 Obtaining higher precision ............................ 121
6 Difficulties with transition probabilities ................. 123
6.1 Eliminating undesirable states ........................ 123
6.2 The k-core of a random graph .......................... 124
6.2.1 The transition probabilities ................... 125
6.2.2 Dealing with difficult differential
equations ...................................... 131
7 Differences with a tail .................................... 136
7.1 The degree-greedy algorithm for independent sets ...... 136
7.2 Greedy packing ........................................ 143
8 Other processes ............................................ 150
Acknowledgements ........................................... 152
References .................................................... 153
| 
