Fall 2017

On a Generalization of Iterated and Randomized Rounding

Monday, December 10th, 2018 2:30 pm3:00 pm

Add to Calendar


Nikhil Bansal (Eindhoven University of Technology)

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.