[Colloquium] REMINDER: 10/31 TTIC Colloquium: Sanjeev Khanna, University of Pennsylvania

[Mary Marre via Colloquium]

When:     Monday, October 31st at 11:00 a.m.

Where:    TTIC, 6045 S. Kenwood Avenue, 5th Floor, Room 526

Who:      Sanjeev Khanna, University of Pennsylvania


Title:      On the Single-Pass Streaming Complexity of the Set Cover Problem

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.

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.

This is joint work with my students Sepehr Assadi and Yang Li.


Host: Julia Chuzhoy, *cjulia at ttic.edu* <cjulia at ttic.edu>



For more information on the colloquium series or to subscribe to the
mailing list, please see http://www.ttic.edu/colloquium.php


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/20161030/449c9c9f/attachment.html>