The author gives a general method for rounding linear programs that combines the commonly used iterated rounding and randomized rounding techniques. In particular, it is shown that whenever iterated rounding can be applied to a problem with some slack, there is a randomized procedure that returns an integral solution that satisfies the guarantees of iterated rounding and also has concentration properties. The author uses this to give new results for several classic problems where iterated rounding has been useful.
Renata is a third-year PhD student at the University of Maryland, College Park, advised by Aravind Srinivasan. Her interests lie in the design and analysis of randomized algorithms, with a focus in dependent rounding and concentration inequalities.