[Colloquium] 10/22 TTIC Colloquium: Nikhil Bansal, Eindhoven University of Technology

[Mary Marre via Colloquium]

*When:    *  Monday, October 22nd at 11:00 am

*Where:     *TTIC, 6045 S. Kenwood Avenue, 5th Floor, Room 526



*Who:        *Nikhil Bansal, Eindhoven University of Technology



*Title:       *On a generalization of iterated and randomized rounding

*Abstract:* Randomized rounding and iterated rounding are perhaps the two
most commonly

used techniques in approximation algorithms. However, they are based on
very different approaches:

one is probabilistic and the other is linear algebraic.

I will describe a new rounding procedure that unifies both these
methods, and significantly extends

the reach of currently known dependent-rounding methods. In the talk, we
will see how this leads

to various new results for several classic problems such as degree-bounded
spanning trees,

rounding column sparse linear programs  and load-balancing on unrelated
machines.

Host: Avrim Blum <avrim at ttic>


For more information on the colloquium series or to subscribe to the
mailing list, please see http://www.ttic.edu/colloquium.php



Mary C. Marre
Administrative Assistant
*Toyota Technological Institute*
*6045 S. Kenwood Avenue*
*Room 517*
*Chicago, IL  60637*
*p:(773) 834-1757*
*f: (773) 357-6970*
*mmarre at ttic.edu <mmarre at ttic.edu>*
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20181015/a991dfaf/attachment.html>