Approximation algorithms via randomized rounding: a survey

TitleApproximation algorithms via randomized rounding: a survey
Publication TypeJournal Articles
Year of Publication1999
AuthorsSrinivasan A
JournalLectures on Approximation and Randomized Algorithms (M. Karonski and HJ Promel, editors), Series in Advanced Topics in Mathematics, Polish Scientific Publishers PWN
Pagination9 - 71
Date Published1999///

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.