Seminar Event Detail

Theoretical Computer Science

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
Institution:  U-M

Event Organizer:      schoeneb


Edit this event (login required).
Add new event (login required).
For access requests and instructions, contact

Back to previous page
Back to UM Math seminars/events page.