[Colloquium] 5/3 Talks at TTIC: Chandra Chekuri, UIUC

[Mary Marre via Colloquium]

 *When:  *   Thursday, May 3rd at *3:30 pm*

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

*Who: *      Chandra Chekuri, UIUC


*Title:* Tree Packing, Global Mincut, and Faster Algorithms for Metric-TSP
and Related Problems

*Abstract:* We will discuss some recent work on faster approximation
schemes for solving LP relaxations via the multiplicative weight update
method. The focus will be on some concrete applications. We will discuss a
near-linear time algorithms for fractional tree packing in a capacitated
graph and its connection to Karger's near-linear time global mincut
algorithm. We will also discuss how the global mincut algorithm can be
adapted into the MWU framework to derive a near-linear time approximation
scheme for the well-known LP for Metric-TSP.

Joint work with Kent Quanrud.


Host: Avrim Blum <avrim at ttic.edu>


Mary C. Marre
Administrative Assistant
*Toyota Technological Institute*
*6045 S. Kenwood Avenue*
*Room 504*
*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/20180430/9f523427/attachment.html>