Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:Semi-Streaming Set Cover
Speaker:Adi Rosén
coming from:IRIF (Université Paris Diderot - Paris 7 )
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
Visibility:D1, D2, D3, D4, D5, RG1, SWS, MMCI
We use this to send out email in the morning.
Level:AG Audience
Date, Time and Location
Date:Thursday, 2 March 2017
Duration:30 Minutes
Building:E1 4 - MPI-INF
In this talk I will discuss algorithms and lower bounds for the classical set cover problem, in streaming settings.

The problem is that of a stream of subsets of an underlying universe of size $n$, each set given by the list of elements it includes. The goal of the algorithm is that of finding (approximations of) minimum covers of the universe, or merely estimating the size of minimum covers, under the constraint that the algorithm can use only limited space.
This space is typically limited by $O(n {polylog}n)$ bits, a constraint referred to as semi-streaming.

I will concentrate on the basic setting of a single-pass semi-streaming algorithm, and the basic problems of finding a family of sets of minimum cardinality (or cost, in the weighted case), that covers the whole universe, or only a $(1-\epsilon)$-fraction of the universe, for some $0 \leq \epsilon < 1$. For this problem we give an asymptotically tight trade-off between $\epsilon$ and the approximation ratio: We design a semi-streaming algorithm that constructs a succinct data structure $D$ from which one can extract, for every $0 \leq \epsilon < 1$, a $(1 - \epsilon)$-cover that approximates the optimal 1-cover within a factor of $f(\epsilon, n)$, where $f(\epsilon, n)= O(1/\epsilon)$ if $ \epsilon > 1 / \sqrt{n}$, and $f(\epsilon, n)=O (\sqrt{n})$ otherwise. In particular for the traditional set cover problem of covering the whole universe we obtain an $O(\sqrt{n})$-approximation. This algorithm is proved to be best possible for any randomized algorithm by establishing a family (parameterized by $\epsilon$) of matching lower bounds.

I will then shortly review several subsequent results that later extended our work to the case of multiple passes on the stream, and to the problem of only estimating the size of the cover, in particular giving lower bounds on the decision-problem variant. I will further point out a number of open questions about the set cover problem in streaming settings.

Joint work with Yuval Emek.

Name(s):Moti Medina
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):

Moti Medina, 02/23/2017 01:22 PM
Last modified:
Uwe Brahm/MPII/DE, 03/02/2017 07:01 AM
  • Moti Medina, 02/24/2017 10:48 AM
  • Moti Medina, 02/23/2017 01:22 PM -- Created document.