Discrete Mathematics and Optimization Seminar
May 1st, 2009
MC 320, 2:30 PM
Dependent Rounding and Approximation Algorithms.
Aravind Srinivasan
University of Maryland, College Park
We present a randomized-rounding approach for fractional vectors defined on the edge-sets of bipartite graphs. We sketch various ways of combining this technique with other ideas, leading to improved approximation algorithms in routing, scheduling, and auctions. This talk will cover papers of the speaker and his co-authors, that appeared in APPROX 2008, FOCS 2005, FOCS 2002, and FOCS 2001.