Randomized and Approximation Algorithms

Several practically relevant algorithmic problems are unfortunately not known to have deterministic efficient algorithms. More specifically, for several important problems, it is highly unlikely that an efficient algorithm exists that produces an optimal solution on every input instance. Since often such problems are too important to be left unadressed, there are several "relaxations" being used to adress such problems. Two of them are:

• Approximation Algorithms: One can relax the objective of searching for the optimal solution and instead design an efficient algorithm that produces solutions which are provably "close" in value to the optimal one.
• Randomized Algorithms, and Probabilistic Analysis of Algorithms: Often, allowing an algorithm to make random choices during its execution leads to significantly more efficient computation (possibly with the drawback that the efficiency is only guaranteed with some probability, or that the output is correct only with some probability). Especially in the context of approximation algorithms, such randomized methods provide powerful tools.  Furthermore, many problems are known to be difficult only in specific, pathetic instances whereas for instances apearing in practice efficient algorithms may exist. Probabilistic analysis of algorithms can, in many cases, give a theoretical explanation of this phenomenon.

In this course we will focus on several techniques for designing and analyzing randomized and approximation algorithms. We will also see a couple of interesting recent results in the area.