A case study of de-randomization methods for combinatorial approximation algorithms

We study three different de-randomization methods that are often applied to approximate combinatorial optimization problems. We analyze the conditiona l probabilities method in connection with randomized rounding for routing, packing and covering integer linear programming problems. We show extension s of such methods for non-independent randomized rounding for the assignmen t problem. The second method, the so-called random walks is exemplified wit h algorithms for dense instances of some NP problems. Another often used me thod is the bounded independence technique; we explicit this method for the sparsest cut and maximum concurrent flow problems.