<div dir="ltr"><div><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 Khanna, University of Pennsylvania</font></div></div></div><div><br></div><div><br></div><div>Title:      On the Single-Pass Streaming Complexity of the Set Cover Problem</div><div><br></div><div>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><br></div><div>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><br></div><div>This is joint work with my students Sepehr Assadi and Yang Li.</div><div><br></div><div><br></div><div>Host: Julia Chuzhoy, <a href="mailto:cjulia@ttic.edu"><font color="#0000ff"><b><span style="font-family:"normal arial",sans-serif;font-size:12px">cjulia</span><wbr style="font-family:"normal arial",sans-serif;font-size:12px"><span style="font-family:"normal arial",sans-serif;font-size:12px">@ttic.edu</span></b></font></a></div><div><br></div><div><br></div><div><br></div><div><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><br></div><div><br></div><div><br></div><div><br></div><div><div class="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>