Talks
Fall 2017

On a Generalization of Iterated and Randomized Rounding

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

Add to Calendar

Speaker: 

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.