<div dir="ltr"><div style="font-size:12.8px"><p class="MsoNormal" style="margin-bottom:0.0001pt;font-size:12.8px;line-height:normal"><span style="font-size:12.8px"><font face="arial, helvetica, sans-serif">When:     <span class="gmail-m_3780754808999067173gmail-m_681982430442049102gmail-m_7957711656738355323gmail-m_-3334114423867790755gmail-m_-9149867449940684394gmail-m_-2475804285784780919gmail-m_-7164114494009287624gmail-m_-7229391482845024438gmail-m_7776827232588711945gmail-m_-3320638437953326758gmail-m_3990498715904616980gmail-il"><span class="gmail-m_3780754808999067173gmail-m_681982430442049102gmail-m_7957711656738355323gmail-il">Friday</span></span>, April 21st at noon</font></span></p><p class="MsoNormal" style="margin-bottom:0.0001pt;font-size:12.8px;line-height:normal"><font face="arial, helvetica, sans-serif"> </font></p><p class="MsoNormal" style="margin-bottom:0.0001pt;font-size:12.8px;line-height:normal"><font face="arial, helvetica, sans-serif">Where:    TTIC, 6045 S Kenwood Avenue, 5th Floor, Room 526</font></p><p class="MsoNormal" style="margin-bottom:0.0001pt;font-size:12.8px;line-height:normal"><font face="arial, helvetica, sans-serif"> </font></p><p class="MsoNormal" style="margin-bottom:0.0001pt;font-size:12.8px;line-height:normal"><font face="arial, helvetica, sans-serif">Who:       Julia Chuzhoy; TTIC</font></p></div><div style="font-size:12.8px"><font face="arial, helvetica, sans-serif"><br></font></div><div style="font-size:12.8px"><font face="arial, helvetica, sans-serif"><br></font></div><div style="margin:0px;font-size:13px;line-height:normal"><font face="arial, helvetica, sans-serif">Title: New Approximation Algorithms and Hardness Results for Graph Routing Problems</font></div><div style="margin:0px;font-size:13px;line-height:normal;min-height:15px"><font face="arial, helvetica, sans-serif"><br></font></div><div style="margin:0px;font-size:13px;line-height:normal"><font face="arial, helvetica, sans-serif">Abstract: This talk will mostly focus on the Node-Disjoint Paths problem. This is a basic graph routing problem, in which the input consists of a graph G together with a collection {(s_1,t_1),...,(s_k,t_k)} of pairs of its vertices, called demand pairs. The goal is to connect as many of the demand pairs as possible by paths that are disjoint in both their edges and vertices. Until recently, the approximability of this problem was widely open: a simple greedy O(\sqrt n)-approximaiton algorithm was the best known algorithm even for restricted special cases of the problem, such as planar graphs and grid graphs. On the negative side, only roughly \Omega(\sqrt{\log n})-hardness of approximation was known for general graphs, and only APX-hardness for planar graphs and grids. In this talk we will survey several recent developments on both the algorithmic and hardness of approximation fronts, that come close to resolving the approximation complexity of this problem, in a somewhat surprising way.</font></div><div style="margin:0px;font-size:13px;line-height:normal;min-height:15px"><font face="arial, helvetica, sans-serif"><br></font></div><div style="margin:0px;font-size:13px;line-height:normal;min-height:15px"><font face="arial, helvetica, sans-serif"><br></font></div><div style="margin:0px;font-size:13px;line-height:normal"><font face="arial, helvetica, sans-serif">Based on joint work with David H. K. Kim, Shi Li and Rachit Nimavat.</font></div><div style="margin:0px;font-size:13px;line-height:normal"><font face="arial, helvetica, sans-serif"><br></font></div><div style="margin:0px;font-size:13px;line-height:normal;font-family:arial"><br></div><div style="margin:0px;font-size:13px;line-height:normal;font-family:arial"><b style="font-family:arial,sans-serif;font-size:12.8px"><font face="arial, helvetica, sans-serif">******************************<wbr>******************************<wbr>******************************<wbr>************</font></b><br></div><div style="margin:0px;font-size:13px;line-height:normal;font-family:arial"><div class="gmail_default" style="font-family:arial,sans-serif;font-size:12.8px"><b><font face="arial, helvetica, sans-serif"><br></font></b></div><div class="gmail_default" style="font-family:arial,sans-serif;font-size:12.8px"><b><font face="arial, helvetica, sans-serif"><span class="gmail-m_3780754808999067173gmail-m_681982430442049102gmail-m_7957711656738355323gmail-m_-3334114423867790755gmail-m_-9149867449940684394gmail-il">Research</span> at <span class="gmail-m_3780754808999067173gmail-m_681982430442049102gmail-m_7957711656738355323gmail-m_-3334114423867790755gmail-m_-9149867449940684394gmail-il">TTIC</span> Seminar Series</font></b></div><div class="gmail_default" style="font-family:arial,sans-serif;font-size:12.8px"><font face="arial, helvetica, sans-serif"> </font></div><div class="gmail_default" style="font-family:arial,sans-serif;font-size:12.8px"><font face="arial, helvetica, sans-serif"><span class="gmail-m_3780754808999067173gmail-m_681982430442049102gmail-m_7957711656738355323gmail-m_-3334114423867790755gmail-m_-9149867449940684394gmail-il">TTIC</span> is hosting a weekly seminar series presenting the <span class="gmail-m_3780754808999067173gmail-m_681982430442049102gmail-m_7957711656738355323gmail-m_-3334114423867790755gmail-m_-9149867449940684394gmail-il">research</span> currently underway at the Institute. Every week a different <span class="gmail-m_3780754808999067173gmail-m_681982430442049102gmail-m_7957711656738355323gmail-m_-3334114423867790755gmail-m_-9149867449940684394gmail-il">TTIC</span> faculty member will present their <span class="gmail-m_3780754808999067173gmail-m_681982430442049102gmail-m_7957711656738355323gmail-m_-3334114423867790755gmail-m_-9149867449940684394gmail-il">research</span>.  The lectures are intended both for students seeking <span class="gmail-m_3780754808999067173gmail-m_681982430442049102gmail-m_7957711656738355323gmail-m_-3334114423867790755gmail-m_-9149867449940684394gmail-il">research</span> topics and adviser, and for the general <span class="gmail-m_3780754808999067173gmail-m_681982430442049102gmail-m_7957711656738355323gmail-m_-3334114423867790755gmail-m_-9149867449940684394gmail-il">TTIC</span> and University of Chicago communities interested in hearing what their colleagues are up to.   </font></div><div class="gmail_default" style="font-family:arial,sans-serif;font-size:12.8px"><font face="arial, helvetica, sans-serif"> </font></div><div class="gmail_default" style="font-family:arial,sans-serif;font-size:12.8px"><font face="arial, helvetica, sans-serif">To receive announcements about the seminar series, please subscribe to the mailing list: <a href="https://groups.google.com/a/ttic.edu/group/talks/subscribe" target="_blank">https://groups.google.co<wbr>m/a/<span class="gmail-m_3780754808999067173gmail-m_681982430442049102gmail-m_7957711656738355323gmail-m_-3334114423867790755gmail-m_-9149867449940684394gmail-il">ttic</span>.edu/group/<span class="gmail-m_3780754808999067173gmail-m_681982430442049102gmail-m_7957711656738355323gmail-m_-3334114423867790755gmail-m_-9149867449940684394gmail-m_-145227099154046382gmail-m_-7164114494009287624gmail-m_-7229391482845024438gmail-m_7776827232588711945gmail-m_-3320638437953326758gmail-m_3990498715904616980gmail-m_-8247393949946928606gmail-m_-8480526344443392316gmail-m_-1056553444316568634gmail-m_593248408351034154gmail-m_8873931552348078312gmail-m_-3900280345830708483gmail-m_2412953322955092339gmail-m_-3568727914368024249gmail-m_-7538648194147727859gmail-il"><span class="gmail-m_3780754808999067173gmail-m_681982430442049102gmail-m_7957711656738355323gmail-m_-3334114423867790755gmail-m_-9149867449940684394gmail-m_-145227099154046382gmail-m_-7164114494009287624gmail-m_-7229391482845024438gmail-m_7776827232588711945gmail-m_-3320638437953326758gmail-m_3990498715904616980gmail-m_-8247393949946928606gmail-m_-8480526344443392316gmail-m_-1056553444316568634gmail-m_593248408351034154gmail-m_8873931552348078312gmail-m_-3900280345830708483gmail-m_2412953322955092339gmail-m_-3568727914368024249gmail-il"><span class="gmail-m_3780754808999067173gmail-m_681982430442049102gmail-m_7957711656738355323gmail-m_-3334114423867790755gmail-m_-9149867449940684394gmail-m_-145227099154046382gmail-m_-7164114494009287624gmail-m_-7229391482845024438gmail-m_7776827232588711945gmail-m_-3320638437953326758gmail-m_3990498715904616980gmail-il"><span class="gmail-m_3780754808999067173gmail-m_681982430442049102gmail-m_7957711656738355323gmail-m_-3334114423867790755gmail-m_-9149867449940684394gmail-m_-145227099154046382gmail-m_-7164114494009287624gmail-il"><span class="gmail-m_3780754808999067173gmail-m_681982430442049102gmail-m_7957711656738355323gmail-il">talks</span></span></span></span></span>/subsc<wbr>ribe</a></font></div><div class="gmail_default" style="font-family:arial,sans-serif;font-size:12.8px"><font face="arial, helvetica, sans-serif"><br></font></div><div class="gmail_default" style="font-family:arial,sans-serif;font-size:12.8px"><font face="arial, helvetica, sans-serif">Speaker details can be found at: <a href="http://www.ttic.edu/tticseminar.php" target="_blank">http://www.<span class="gmail-m_3780754808999067173gmail-m_681982430442049102gmail-m_7957711656738355323gmail-m_-3334114423867790755gmail-m_-9149867449940684394gmail-il">ttic</span>.edu/tticse<wbr>minar.php</a>.</font></div><div class="gmail_default" style="font-family:arial,sans-serif;font-size:12.8px"><font face="arial, helvetica, sans-serif"> </font></div><div class="gmail_default" style="font-family:arial,sans-serif;font-size:12.8px"><font face="arial, helvetica, sans-serif">For additional questions, please contact Nathan Srebro at <a href="mailto:mcallester@ttic.edu" target="_blank">nati@<span class="gmail-m_3780754808999067173gmail-m_681982430442049102gmail-m_7957711656738355323gmail-m_-3334114423867790755gmail-m_-9149867449940684394gmail-il">ttic</span>.edu</a> </font></div></div><div style="margin:0px;font-size:13px;line-height:normal;font-family:arial"><br></div><div style="margin:0px;font-size:13px;line-height:normal;font-family:arial"><br></div><div style="margin:0px;font-size:13px;line-height:normal;font-family:arial"><br></div><div class="gmail_extra"><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>
<br><div class="gmail_quote">On Fri, Apr 14, 2017 at 2:25 PM, Mary Marre <span dir="ltr"><<a href="mailto:mmarre@ttic.edu" target="_blank">mmarre@ttic.edu</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div><p class="MsoNormal" style="margin-bottom:0.0001pt;font-size:12.8px;line-height:normal"><span style="font-size:12.8px"><font face="arial, helvetica, sans-serif">When:     <span class="m_3780754808999067173gmail-m_681982430442049102gmail-m_7957711656738355323gmail-m_-3334114423867790755gmail-m_-9149867449940684394gmail-m_-2475804285784780919gmail-m_-7164114494009287624gmail-m_-7229391482845024438gmail-m_7776827232588711945gmail-m_-3320638437953326758gmail-m_3990498715904616980gmail-il"><span class="m_3780754808999067173gmail-m_681982430442049102gmail-m_7957711656738355323gmail-il">Friday</span></span>, April 21st at noon</font></span></p><p class="MsoNormal" style="margin-bottom:0.0001pt;font-size:12.8px;line-height:normal"><font face="arial, helvetica, sans-serif"> </font></p><p class="MsoNormal" style="margin-bottom:0.0001pt;font-size:12.8px;line-height:normal"><font face="arial, helvetica, sans-serif">Where:    TTIC, 6045 S Kenwood Avenue, 5th Floor, Room 526</font></p><p class="MsoNormal" style="margin-bottom:0.0001pt;font-size:12.8px;line-height:normal"><font face="arial, helvetica, sans-serif"> </font></p><p class="MsoNormal" style="margin-bottom:0.0001pt;font-size:12.8px;line-height:normal"><font face="arial, helvetica, sans-serif">Who:       Julia Chuzhoy; TTIC</font></p></div><div><font face="arial, helvetica, sans-serif"><br></font></div><div><font face="arial, helvetica, sans-serif"><br></font></div><div style="margin:0px;font-size:13px;line-height:normal"><font face="arial, helvetica, sans-serif">Title: New Approximation Algorithms and Hardness Results for Graph Routing Problems</font></div><div style="margin:0px;font-size:13px;line-height:normal;min-height:15px"><font face="arial, helvetica, sans-serif"><br></font></div><div style="margin:0px;font-size:13px;line-height:normal"><font face="arial, helvetica, sans-serif">Abstract: This talk will mostly focus on the Node-Disjoint Paths problem. This is a basic graph routing problem, in which the input consists of a graph G together with a collection {(s_1,t_1),...,(s_k,t_k)} of pairs of its vertices, called demand pairs. The goal is to connect as many of the demand pairs as possible by paths that are disjoint in both their edges and vertices. Until recently, the approximability of this problem was widely open: a simple greedy O(\sqrt n)-approximaiton algorithm was the best known algorithm even for restricted special cases of the problem, such as planar graphs and grid graphs. On the negative side, only roughly \Omega(\sqrt{\log n})-hardness of approximation was known for general graphs, and only APX-hardness for planar graphs and grids. In this talk we will survey several recent developments on both the algorithmic and hardness of approximation fronts, that come close to resolving the approximation complexity of this problem, in a somewhat surprising way.</font></div><div style="margin:0px;font-size:13px;line-height:normal;min-height:15px"><font face="arial, helvetica, sans-serif"><br></font></div><div style="margin:0px;font-size:13px;line-height:normal;min-height:15px"><font face="arial, helvetica, sans-serif"><br></font></div><div style="margin:0px;font-size:13px;line-height:normal"><font face="arial, helvetica, sans-serif">Based on joint work with David H. K. Kim, Shi Li and Rachit Nimavat.</font></div><div style="margin:0px;font-size:13px;line-height:normal"><font face="arial, helvetica, sans-serif"><br></font></div><div style="margin:0px;font-size:13px;line-height:normal;font-family:arial"><br></div><div style="margin:0px;font-size:13px;line-height:normal;font-family:arial"><b style="font-family:arial,sans-serif;font-size:12.8px"><font face="arial, helvetica, sans-serif">******************************<wbr>******************************<wbr>******************************<wbr>************</font></b><br></div><div style="margin:0px;font-size:13px;line-height:normal;font-family:arial"><div style="font-family:arial,sans-serif;font-size:12.8px"><b><font face="arial, helvetica, sans-serif"><br></font></b></div><div style="font-family:arial,sans-serif;font-size:12.8px"><b><font face="arial, helvetica, sans-serif"><span class="m_3780754808999067173gmail-m_681982430442049102gmail-m_7957711656738355323gmail-m_-3334114423867790755gmail-m_-9149867449940684394gmail-il">Research</span> at <span class="m_3780754808999067173gmail-m_681982430442049102gmail-m_7957711656738355323gmail-m_-3334114423867790755gmail-m_-9149867449940684394gmail-il">TTIC</span> Seminar Series</font></b></div><div style="font-family:arial,sans-serif;font-size:12.8px"><font face="arial, helvetica, sans-serif"> </font></div><div style="font-family:arial,sans-serif;font-size:12.8px"><font face="arial, helvetica, sans-serif"><span class="m_3780754808999067173gmail-m_681982430442049102gmail-m_7957711656738355323gmail-m_-3334114423867790755gmail-m_-9149867449940684394gmail-il">TTIC</span> is hosting a weekly seminar series presenting the <span class="m_3780754808999067173gmail-m_681982430442049102gmail-m_7957711656738355323gmail-m_-3334114423867790755gmail-m_-9149867449940684394gmail-il">research</span> currently underway at the Institute. Every week a different <span class="m_3780754808999067173gmail-m_681982430442049102gmail-m_7957711656738355323gmail-m_-3334114423867790755gmail-m_-9149867449940684394gmail-il">TTIC</span> faculty member will present their <span class="m_3780754808999067173gmail-m_681982430442049102gmail-m_7957711656738355323gmail-m_-3334114423867790755gmail-m_-9149867449940684394gmail-il">research</span>.  The lectures are intended both for students seeking <span class="m_3780754808999067173gmail-m_681982430442049102gmail-m_7957711656738355323gmail-m_-3334114423867790755gmail-m_-9149867449940684394gmail-il">research</span> topics and adviser, and for the general <span class="m_3780754808999067173gmail-m_681982430442049102gmail-m_7957711656738355323gmail-m_-3334114423867790755gmail-m_-9149867449940684394gmail-il">TTIC</span> and University of Chicago communities interested in hearing what their colleagues are up to.   </font></div><div style="font-family:arial,sans-serif;font-size:12.8px"><font face="arial, helvetica, sans-serif"> </font></div><div style="font-family:arial,sans-serif;font-size:12.8px"><font face="arial, helvetica, sans-serif">To receive announcements about the seminar series, please subscribe to the mailing list: <a href="https://groups.google.com/a/ttic.edu/group/talks/subscribe" target="_blank">https://groups.google.co<wbr>m/a/<span class="m_3780754808999067173gmail-m_681982430442049102gmail-m_7957711656738355323gmail-m_-3334114423867790755gmail-m_-9149867449940684394gmail-il">ttic</span>.edu/group/<span class="m_3780754808999067173gmail-m_681982430442049102gmail-m_7957711656738355323gmail-m_-3334114423867790755gmail-m_-9149867449940684394gmail-m_-145227099154046382gmail-m_-7164114494009287624gmail-m_-7229391482845024438gmail-m_7776827232588711945gmail-m_-3320638437953326758gmail-m_3990498715904616980gmail-m_-8247393949946928606gmail-m_-8480526344443392316gmail-m_-1056553444316568634gmail-m_593248408351034154gmail-m_8873931552348078312gmail-m_-3900280345830708483gmail-m_2412953322955092339gmail-m_-3568727914368024249gmail-m_-7538648194147727859gmail-il"><span class="m_3780754808999067173gmail-m_681982430442049102gmail-m_7957711656738355323gmail-m_-3334114423867790755gmail-m_-9149867449940684394gmail-m_-145227099154046382gmail-m_-7164114494009287624gmail-m_-7229391482845024438gmail-m_7776827232588711945gmail-m_-3320638437953326758gmail-m_3990498715904616980gmail-m_-8247393949946928606gmail-m_-8480526344443392316gmail-m_-1056553444316568634gmail-m_593248408351034154gmail-m_8873931552348078312gmail-m_-3900280345830708483gmail-m_2412953322955092339gmail-m_-3568727914368024249gmail-il"><span class="m_3780754808999067173gmail-m_681982430442049102gmail-m_7957711656738355323gmail-m_-3334114423867790755gmail-m_-9149867449940684394gmail-m_-145227099154046382gmail-m_-7164114494009287624gmail-m_-7229391482845024438gmail-m_7776827232588711945gmail-m_-3320638437953326758gmail-m_3990498715904616980gmail-il"><span class="m_3780754808999067173gmail-m_681982430442049102gmail-m_7957711656738355323gmail-m_-3334114423867790755gmail-m_-9149867449940684394gmail-m_-145227099154046382gmail-m_-7164114494009287624gmail-il"><span class="m_3780754808999067173gmail-m_681982430442049102gmail-m_7957711656738355323gmail-il">talks</span></span></span></span></span>/subsc<wbr>ribe</a></font></div><div style="font-family:arial,sans-serif;font-size:12.8px"><font face="arial, helvetica, sans-serif"><br></font></div><div style="font-family:arial,sans-serif;font-size:12.8px"><font face="arial, helvetica, sans-serif">Speaker details can be found at: <a href="http://www.ttic.edu/tticseminar.php" target="_blank">http://www.<span class="m_3780754808999067173gmail-m_681982430442049102gmail-m_7957711656738355323gmail-m_-3334114423867790755gmail-m_-9149867449940684394gmail-il">ttic</span>.edu/tticse<wbr>minar.php</a>.</font></div><div style="font-family:arial,sans-serif;font-size:12.8px"><font face="arial, helvetica, sans-serif"> </font></div><div style="font-family:arial,sans-serif;font-size:12.8px"><font face="arial, helvetica, sans-serif">For additional questions, please contact Nathan Srebro at <a href="mailto:mcallester@ttic.edu" target="_blank">nati@<span class="m_3780754808999067173gmail-m_681982430442049102gmail-m_7957711656738355323gmail-m_-3334114423867790755gmail-m_-9149867449940684394gmail-il">ttic</span>.edu</a> </font></div></div><div style="margin:0px;font-size:13px;line-height:normal;font-family:arial"><br></div><div style="margin:0px;font-size:13px;line-height:normal;font-family:arial"><br></div><div style="margin:0px;font-size:13px;line-height:normal;font-family:arial"><br></div><div style="margin:0px;font-size:13px;line-height:normal;font-family:arial"><br></div><div style="margin:0px;font-size:13px;line-height:normal;font-family:arial"><br></div><div><div class="m_3780754808999067173gmail_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:<a href="tel:(773)%20834-1757" value="+17738341757" target="_blank">(773) 834-1757</a></font></i></div><div><i><font face="arial, helvetica, sans-serif">f: <a href="tel:(773)%20357-6970" value="+17733576970" target="_blank">(773) 357-6970</a></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>
</blockquote></div><br></div></div>