Talks
Spring 2017

A Survey of Dependent Rounding

Monday, September 11th, 2017, 9:30 am10:30 am

Add to Calendar

Speaker: 

Aravind Srinivasan, University of Maryland

Dependent rounding, originating from the "pipage rounding" work of Ageev and Sviridenko, is now a fundamental algorithmic approach in combinatorial optimization. We survey this area, with an emphasis on the types of correlation inequalities that are achievable/desirable, and applications thereof. Topics covered include connections with matroids, matroid intersection, and scheduling, as well as how to handle situations where some amount of positive correlation is inevitable: the last part is recent joint work with David Harris, Thomas Pensyl, and Khoa Trinh, and arises in facility-location problems.