License
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICDT.2017.22
URN: urn:nbn:de:0030-drops-70620
URL: http://drops.dagstuhl.de/opus/volltexte/2017/7062/
Go to the corresponding LIPIcs Volume Portal


McGregor, Andrew ; Vu, Hoa T.

Better Streaming Algorithms for the Maximum Coverage Problem

pdf-format:
LIPIcs-ICDT-2017-22.pdf (0.6 MB)


Abstract

We study the classic NP-Hard problem of finding the maximum k-set coverage in the data stream model: given a set system of m sets that are subsets of a universe {1,...,n}, find the k sets that cover the most number of distinct elements. The problem can be approximated up to a factor 1-1/e in polynomial time. In the streaming-set model, the sets and their elements are revealed online. The main goal of our work is to design algorithms, with approximation guarantees as close as possible to 1-1/e, that use sublinear space o(mn). Our main results are: 1) Two (1-1/e-epsilon) approximation algorithms: One uses O(1/epsilon) passes and O(k/epsilon^2 polylog(m,n)) space whereas the other uses only a single pass but O(m/epsilon^2 polylog(m,n)) space. 2) We show that any approximation factor better than (1-(1-1/k)^k) in constant passes require space that is linear in m for constant k even if the algorithm is allowed unbounded processing time. We also demonstrate a single-pass, (1-epsilon) approximation algorithm using O(m/epsilon^2 min(k,1/epsilon) polylog(m,n)) space. We also study the maximum k-vertex coverage problem in the dynamic graph stream model. In this model, the stream consists of edge insertions and deletions of a graph on N vertices. The goal is to find k vertices that cover the most number of distinct edges. We show that any constant approximation in constant passes requires space that is linear in N for constant k whereas O(N/epsilon^2 polylog(m,n)) space is sufficient for a (1-epsilon) approximation and arbitrary k in a single pass. For regular graphs, we show that O(k/epsilon^3 polylog(m,n)) space is sufficient for a (1-epsilon) approximation in a single pass. We generalize this to a K-epsilon approximation when the ratio between the minimum and maximum degree is bounded below by K.

BibTeX - Entry

@InProceedings{mcgregor_et_al:LIPIcs:2017:7062,
  author =	{Andrew McGregor and Hoa T. Vu},
  title =	{{Better Streaming Algorithms for the Maximum Coverage Problem}},
  booktitle =	{20th International Conference on Database Theory (ICDT 2017)},
  pages =	{22:1--22:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-024-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{68},
  editor =	{Michael Benedikt and Giorgio Orsi},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7062},
  URN =		{urn:nbn:de:0030-drops-70620},
  doi =		{10.4230/LIPIcs.ICDT.2017.22},
  annote =	{Keywords: algorithms, data streams, approximation, maximum coverage}
}

Keywords: algorithms, data streams, approximation, maximum coverage
Seminar: 20th International Conference on Database Theory (ICDT 2017)
Issue Date: 2017
Date of publication: 14.03.2017


DROPS-Home | Fulltext Search | Imprint Published by LZI