Institut de Recherche en Informatique Fondamentale


IRIF

L'IRIF est une unité mixe de recherche (UMR 8243) du CNRS et de l'Université Paris-Diderot, issue de la fusion des deux UMR LIAFA et PPS au 1er janvier 2016. Ses objectifs scientifiques se déclinent selon trois grandes thématiques au cœur de l'informatique : les fondements mathématiques de l’informatique ; les modèles de calcul et de preuves ; la modélisation, les algorithmes et la conception de systèmes.



Prochains séminaires


Lundi 29 août 2016 · 11h00 · Room 2002

Algorithmes et complexité · Sanjeev Khanna (University of Pennsylvania) · On the Single-Pass Streaming Complexity of the Set Cover Problem

In the set cover problem, we are given a collection of $m$ subsets over a universe of $n$ elements, and the goal is to find a sub-collection of 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 the goal is to solve the set cover problem using a space-efficient algorithm.

We show that to compute an $\alpha$-approximate set cover (for any $\alpha= o(\sqrt{n})$) via a single-pass streaming algorithm, $\Theta(mn/\alpha)$ space is both necessary and sufficient (up to an $O(\log{n})$ factor). We further study the problem of estimating the size of a minimum set cover (as opposed to finding the actual sets), and show that this turns out to be a distinctly easier problem. Specifically, we prove that $\Theta(mn/\alpha^2)$ space is both sufficient and necessary (up to logarithmic factors) for estimating the size of a minimum set cover to within a factor of $\alpha$. Our algorithm in fact works for the more general problem of estimating the optimal value of a covering integer program. These results provide a tight resolution of the space-approximation tradeoff for single-pass streaming algorithms for the set cover problem.

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



Événements


Mercredi 7 – Vendredi 9 septembre 2016 · Institut Henri Poincaré (IHP)

Approx-Random 2016


Dimanche 15 - Vendredi 20 Janvier 2017 · Jussieu

POPL 2017



Organismes de tutelle


Université Paris-Diderot – Paris 7

CNRS


UFR de rattachement

Partenaires


Fédération de Recherche en Mathématiques de Paris Centre

Fondation Sciences Mathématiques de Paris

INRIA