Tamás Kis:
Randomized algorithms
Randomization in the design of approximation algorithms has proved an extremely powerful tool. In the lectures we will see a number of examples when the best approximation results are achieved by using coin tosses. On top of that, in many cases randomized algorithms can be "derandomized" without sacrificing solution quality, thus obtaining the best deterministic algorithms.