Approximation algorithms via randomized rounding: a survey

Approximation algorithms provide a natural way to approach computationally hardproblems. There are currently many known paradigms in this area, including greedy al-
gorithms, primal-dual methods, methods based on mathematical programming (linear
and semide nite programming in particular), local improvement, and \low distortion"
embeddings of general metric spaces into special families of metric spaces. Random-
ization is a useful ingredient in many of these approaches, and particularly so in the
form of randomized rounding of a suitable relaxation of a given problem. We survey
this technique here, with a focus on correlation inequalities and their applications.