Events Calendar

CS Colloq: Jan Vondrak

Talk Title: Randomized rounding in the matroid polytopeSpeaker: : Dr. Jan Vondrak, IBM AlmadenAbstract:The question how to round a fractional solution in a matroid polytope has emerged recently in various settings, ranging from welfare maximization and max-min allocation problems, to degree-bounded spanning trees and the asymmetric traveling salesman problem. In all these applications, it is useful to have a randomized rounding procedure which in expectation preserves the fractional solution, and satisfies strong concentration bounds for certain functions of the rounded solution. We propose a simple rounding procedure which has the above properties for any matroid and satisfies Chernoff-type concentration bounds for linear functions as well as monotone submodular functions. I will illustrate the usefulness of this technique on various examples.Joint work with Chandra Chekuri (UI Urbana-Champaign) and Rico Zenklusen (ETH Zurich).Bio:Jan Vondrak got his PhD from MIT in 2005, under the supervision of Michel Goemans. He spent 1 year as a postdoc at Microsoft Research and 3 years in the department of mathematics at Princeton University. Since 2009, he has been a research staff member at IBM Almaden.

Location: Seaver Science Library (SSL) - 150

Audiences: Everyone Is Invited

Contact: CS Front Desk