Abstract

Randomized rounding and iterated rounding are perhaps the two most commonly used techniques in approximation algorithms. However, they are based on very different approaches: one is probabilistic and the other is linear algebraic. I will describe a new rounding procedure that unifies both these methods, and significantly extends the reach of currently known dependent-rounding methods. In the talk, we will see how this leads to various new results for several classic problems such as degree-bounded spanning trees, rounding column sparse linear programs and load-balancing on unrelated machines.