[Colloquium] REMINDER: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>*

On Mon, Apr 30, 2018 at 5:33 PM, Mary Marre <mmarre at ttic.edu> wrote:

> *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/20180502/8df76b8a/attachment-0001.html>