Better Streaming Algorithms for the Maximum Coverage Problem
Authors:
- 23 July 2018
- journal article
- research article
- Published by Springer Nature in Theory of Computing Systems
- Vol. 63 (7) , 1595-1619
Abstract
No abstract availableKeywords
All Related Versions
Funding Information
- National Science Foundation (CCF-0953754)
- National Science Foundation (IIS-1251110)
This publication has 44 references indexed in Scilit:
- Spectral Sparsification in Dynamic Graph Streams2013
- Online maximum -coverageDiscrete Applied Mathematics, 2012
- Analyzing Graph Structure via Linear Measurements2012
- Spectral Sparsification of GraphsSIAM Journal on Computing, 2011
- Pipage Rounding: A New Method of Constructing Algorithms with Proven Performance GuaranteeJournal of Combinatorial Optimization, 2004
- Comparing data streams using hamming norms (how to zero in)IEEE Transactions on Knowledge and Data Engineering, 2003
- The budgeted maximum coverage problemInformation Processing Letters, 1999
- A threshold of ln n for approximating set coverJournal of the ACM, 1998
- Randomized Distributed Edge Coloring via an Extension of the Chernoff--Hoeffding BoundsSIAM Journal on Computing, 1997
- Chernoff–Hoeffding Bounds for Applications with Limited IndependenceSIAM Journal on Discrete Mathematics, 1995