|Date: Friday, December 04, 2015
Location: 3725 BBB (10:00 AM to 11:00 AM)
Title: Approximation-Friendly Discrepancy Rounding
Abstract: We consider the general problem of rounding a fractional vector to an integral vector while (approximately) satisfying a number of linear constraints. Randomized rounding and discrepancy-based rounding are two of the strongest rounding methods known. However these algorithms are very different and the bounds achieved by them are incomparable. Randomized rounding leads to good multiplicative bounds, whereas discrepancy-based rounding leads to much better additive bounds. Our first contribution is a new discrepancy-based rounding algorithm that simultaneously yields strong additive as well as multiplicative bounds. Our second contribution is an extension of this rounding algorithm to matroid polytopes. As applications, we obtain new results for low-congestion routing and degree-bounded matroids. This is joint work with Nikhil Bansal.
Speaker: Viswanath Nagarajan
Event Organizer: schoeneb