<div dir="ltr"><div style="font-size:12.8px"><div style="font-size:12.8px"><font face="arial, helvetica, sans-serif"><span style="font-size:12.8px">When:</span><b style="font-size:12.8px"> </b><span style="font-size:12.8px">    </span><span style="font-size:12.8px">Monday, October 31st at 11:00 a.m.</span><span style="font-size:12.8px"> </span><br></font></div><div dir="ltr"><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">Where:    TTIC, 6045 S. Kenwood Avenue, 5th Floor, Room 526</font></div><div style="font-size:12.8px"><font face="arial, helvetica, sans-serif"><br></font></div><div><font face="arial, helvetica, sans-serif" style="font-size:12.8px">Who:      Sanjeev <span class="gmail-m_-8631546152517726394gmail-il">Khanna</span>, University of Pennsylvania</font></div></div></div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px">Title:      On the Single-Pass Streaming Complexity of the Set Cover Problem</div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px">Abstract: In the set cover problem, we are given a collection of sets over a universe of elements, and the goal is to find a sub-collection of these sets whose union covers the universe. The set cover problem is a fundamental optimization problem with many applications in computer science and related disciplines. In this talk, we investigate the set cover problem in the streaming model of computation whereby the sets are presented one by one in a stream, and we wish to find an approximate set cover or simply estimate its size using a space-efficient algorithm.</div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px">We give a tight resolution of the tradeoff between the space available to the algorithm and the quality of the set cover approximation. Our results also extend to the more general problem of estimating the optimal value of a covering integer program presented in a stream.</div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px">This is joint work with my students Sepehr Assadi and Yang Li.</div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px">Host: Julia Chuzhoy, <a href="mailto:cjulia@ttic.edu" target="_blank"><font color="#0000ff"><b><span style="font-family:"normal arial",sans-serif;font-size:12px">cjulia</span><span style="font-family:"normal arial",sans-serif;font-size:12px">@ttic.edu</span></b></font></a></div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px"><span style="font-size:12.8px;font-family:arial,helvetica,sans-serif">For more information on the </span><span style="font-size:12.8px;font-family:arial,helvetica,sans-serif">colloquium</span><span style="font-size:12.8px;font-family:arial,helvetica,sans-serif"> series or to subscribe to the mailing list, please see </span><a href="http://www.ttic.edu/colloquium.php" target="_blank" style="font-size:12.8px;font-family:arial,helvetica,sans-serif">http://www.ttic.edu/colloq<wbr>uium.php</a></div></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 Sun, Oct 30, 2016 at 6:52 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 style="font-size:12.8px"><div style="font-size:12.8px"><font face="arial, helvetica, sans-serif"><span style="font-size:12.8px">When:</span><b style="font-size:12.8px"> </b><span style="font-size:12.8px">    </span><span style="font-size:12.8px">Monday, October 31st at 11:00 a.m.</span><span style="font-size:12.8px"> </span><br></font></div><div dir="ltr"><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">Where:    TTIC, 6045 S. Kenwood Avenue, 5th Floor, Room 526</font></div><div style="font-size:12.8px"><font face="arial, helvetica, sans-serif"><br></font></div><div><font face="arial, helvetica, sans-serif" style="font-size:12.8px">Who:      Sanjeev <span class="m_-8631546152517726394gmail-il">Khanna</span>, University of Pennsylvania</font></div></div></div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px">Title:      On the Single-Pass Streaming Complexity of the Set Cover Problem</div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px">Abstract: In the set cover problem, we are given a collection of sets over a universe of elements, and the goal is to find a sub-collection of these sets whose union covers the universe. The set cover problem is a fundamental optimization problem with many applications in computer science and related disciplines. In this talk, we investigate the set cover problem in the streaming model of computation whereby the sets are presented one by one in a stream, and we wish to find an approximate set cover or simply estimate its size using a space-efficient algorithm.</div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px">We give a tight resolution of the tradeoff between the space available to the algorithm and the quality of the set cover approximation. Our results also extend to the more general problem of estimating the optimal value of a covering integer program presented in a stream.</div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px">This is joint work with my students Sepehr Assadi and Yang Li.</div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px">Host: Julia Chuzhoy, <a href="mailto:cjulia@ttic.edu" target="_blank"><font color="#0000ff"><b><span style="font-family:"normal arial",sans-serif;font-size:12px">cjulia</span><span style="font-family:"normal arial",sans-serif;font-size:12px">@ttic.edu</span></b></font></a></div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px"><span style="font-size:12.8px;font-family:arial,helvetica,sans-serif">For more information on the </span><span style="font-size:12.8px;font-family:arial,helvetica,sans-serif">colloquium</span><span style="font-size:12.8px;font-family:arial,helvetica,sans-serif"> series or to subscribe to the mailing list, please see </span><a href="http://www.ttic.edu/colloquium.php" style="font-size:12.8px;font-family:arial,helvetica,sans-serif" target="_blank">http://www.ttic.edu/colloq<wbr>uium.php</a><br></div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px"><br></div><div><div class="m_-8631546152517726394gmail_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:%28773%29%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:%28773%29%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>