<div dir="ltr">

<div style="color:rgb(34,34,34);font-family:arial,sans-serif;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;text-decoration-style:initial;text-decoration-color:initial;font-size:12.8px">

<div style="color:rgb(34,34,34);font-family:arial,sans-serif;font-size:12.8px;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;text-decoration-style:initial;text-decoration-color:initial"><div class="gmail_default" style="color:rgb(34,34,34);font-size:12.8px;font-family:arial,sans-serif;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;text-decoration-style:initial;text-decoration-color:initial"><font color="#000000" face="arial, helvetica, sans-serif" style=""><b style="background-color:rgb(255,255,255)">When:  </b><span style="background-color:rgb(255,255,255)">   Thursday, May 3rd </span><span class="gmail-m_-6927805759275986140gmail-m_8778633083237298896gmail-m_-8347358208690191418gmail-m_6958947101002467454gmail-m_4240741644540508174gmail-m_-7649362550103587767m_3439038168464703931gmail-m_7186661958014209082gmail-m_-4881373329697077770gmail-m_-2141744242196855365gmail-m_1163836401633243615gmail-m_2148237477730121328gmail-m_-6691959996525573090gmail-m_1517372298344856049gmail-m_491069367152086750gmail-m_-8327640324523575189gmail-m_2420618808463760418gmail-m_7960197898027616883gmail-m_8692226636264124041gmail-m_2794822896869921223gmail-m_7508998950622620526gmail-m_-7153355664495542534gmail-il" style="background-color:rgb(255,255,255);font-weight:400">at</span><span style="background-color:rgb(255,255,255)"> </span><span style="font-weight:400;background-color:rgb(255,255,0)"><b style="">3:30 pm</b></span></font></div><div class="gmail_default" style="background-color:rgb(255,255,255);font-weight:400;color:rgb(34,34,34);font-size:12.8px;font-family:arial,sans-serif;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;text-decoration-style:initial;text-decoration-color:initial"><font color="#000000" face="arial, helvetica, sans-serif"><br></font></div><div class="gmail_default" style="background-color:rgb(255,255,255);color:rgb(34,34,34);font-size:12.8px;font-family:arial,sans-serif;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;text-decoration-style:initial;text-decoration-color:initial"><font color="#000000" face="arial, helvetica, sans-serif"><b>Where: </b>   <span class="gmail-m_-6927805759275986140gmail-m_8778633083237298896gmail-m_-8347358208690191418gmail-m_6958947101002467454gmail-m_4240741644540508174gmail-m_-7649362550103587767m_3439038168464703931gmail-m_7186661958014209082gmail-m_-4881373329697077770gmail-m_-2141744242196855365gmail-m_1163836401633243615gmail-m_2148237477730121328gmail-m_-6691959996525573090gmail-m_1517372298344856049gmail-m_491069367152086750gmail-m_-8327640324523575189gmail-m_2420618808463760418gmail-m_7960197898027616883gmail-m_8692226636264124041gmail-m_2794822896869921223gmail-m_7508998950622620526gmail-m_-7153355664495542534gmail-m_8421504075585210435gmail-m_3262824545120381495gmail-m_-1141671822915777344gmail-m_-7219251726624328345gmail-m_-8588148075564318222gmail-m_-8767966813928691312gmail-m_-1542318334608687154gmail-m_5717104778280916634gmail-m_4845490158781220632gmail-m_5124567205141626540gmail-m_3209361100497750746gmail-m_2953668934074478317gmail-m_-3155518689668024534m_9067904842688472155gmail-m_3071693547520408192gmail-il" style="font-weight:400"><span class="gmail-m_-6927805759275986140gmail-m_8778633083237298896gmail-m_-8347358208690191418gmail-m_6958947101002467454gmail-m_4240741644540508174gmail-m_-7649362550103587767m_3439038168464703931gmail-m_7186661958014209082gmail-m_-4881373329697077770gmail-m_-2141744242196855365gmail-m_1163836401633243615gmail-m_2148237477730121328gmail-m_-6691959996525573090gmail-m_1517372298344856049gmail-m_491069367152086750gmail-m_-8327640324523575189gmail-m_2420618808463760418gmail-m_7960197898027616883gmail-m_8692226636264124041gmail-m_2794822896869921223gmail-m_7508998950622620526gmail-m_-7153355664495542534gmail-il"><span class="gmail-m_-6927805759275986140gmail-m_8778633083237298896gmail-m_-8347358208690191418gmail-m_6958947101002467454gmail-il">TTIC</span></span></span>, 6045 S Kenwood Avenue, 5th Floor, Room 526</font></div><div class="gmail_default" style="background-color:rgb(255,255,255);font-weight:400;color:rgb(34,34,34);font-size:12.8px;font-family:arial,sans-serif;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;text-decoration-style:initial;text-decoration-color:initial"><font face="arial, helvetica, sans-serif"><br></font></div><div style="background-color:rgb(255,255,255);font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;text-decoration-style:initial;text-decoration-color:initial"><font color="#000000" style="color:rgb(34,34,34);font-size:12.8px;font-family:arial,sans-serif;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;letter-spacing:normal;text-transform:none;white-space:normal;word-spacing:0px"><font face="arial, helvetica, sans-serif"><b>Who: </b><span> </span>     </font></font><span class="gmail-il">Chandra</span> Chekuri, UIUC<font color="#000000" style="color:rgb(34,34,34);font-size:12.8px;font-family:arial,sans-serif;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;letter-spacing:normal;text-transform:none;white-space:normal;word-spacing:0px"><font face="arial, helvetica, sans-serif"><br></font></font><font color="#000000" face="arial, helvetica, sans-serif" style="font-weight:400"><br class="gmail-Apple-interchange-newline">

</font></div></div></div><div style="color:rgb(34,34,34);font-family:arial,sans-serif;font-size:12.8px;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial"><br></div><div style="color:rgb(34,34,34);font-family:arial,sans-serif;font-size:12.8px;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial"><b>Title:</b><span style="font-weight:400"> Tree Packing, Global Mincut, and Faster Algorithms for Metric-TSP and Related Problems</span></div><div style="color:rgb(34,34,34);font-family:arial,sans-serif;font-size:12.8px;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial"><br></div><div style="color:rgb(34,34,34);font-family:arial,sans-serif;font-size:12.8px;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial"><b>Abstract:</b><span style="font-weight:400"> We will discuss some recent work on faster approximation schemes </span>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. </div><div style="color:rgb(34,34,34);font-family:arial,sans-serif;font-size:12.8px;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial"><br></div><div style="color:rgb(34,34,34);font-family:arial,sans-serif;font-size:12.8px;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial">Joint work with Kent Quanrud.</div>

<div><br></div><div><br></div><div>Host: <a href="mailto:avrim@ttic.edu">Avrim Blum</a></div><div><br></div><br clear="all"><div><div class="gmail_signature" data-smartmail="gmail_signature"><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><font face="arial, helvetica, sans-serif">Mary C. Marre</font><div><font face="arial, helvetica, sans-serif">Administrative Assistant</font></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6"><b>Toyota Technological Institute</b></font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6">6045 S. Kenwood Avenue</font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6">Room 504</font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6">Chicago, IL  60637</font></i></div><div><i><font face="arial, helvetica, sans-serif">p:(773) 834-1757</font></i></div><div><i><font face="arial, helvetica, sans-serif">f: (773) 357-6970</font></i></div><div><b><i><a href="mailto:mmarre@ttic.edu" target="_blank"><font face="arial, helvetica, sans-serif">mmarre@ttic.edu</font></a></i></b></div></div></div></div></div></div></div></div></div></div>
</div>