|
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.
|
|
|
|