Tight Trade-offs for the Maximum k-Coverage Problem in the General Streaming Model
Summary: Tight (up to polylogs) single-pass space–approximation tradeoff for max k‑coverage in the general edge‑arrival stream: optimal space Θ(m/α^2) for any α>1/(1−1/e). Also gives an Õ(m/α^2 + k)-space algorithm using vector sketches, linking sketching to streaming combinatorial optimization. (summarized by gpt-5-mini on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Piotr Indyk
- 2. Ali Vakilian
Incoming Citations (Sorted by Pagerank)
Showing 1 of 1 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 6,598 | One Set to Cover All Maximal Cliques Approximately | 2022 | SIGMOD | 4.9977108e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 6 of 6 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 383 | An Optimal Algorithm for the Distinct Elements Problem | 2010 | PODS | 0.00024820873 |
| 1,040 | Graph Sketches: Sparsification, Spanners, and Subgraphs | 2012 | PODS | 0.00014488943 |
| 2,749 | Towards Tight Bounds for the Streaming Set Cover Problem | 2016 | PODS | 8.1773535e-05 |
| 2,884 | BPTree: an ℓ2 Heavy Hitters Algorithm Using Constant Memory | 2017 | PODS | 7.9620506e-05 |
| 5,066 | Tight Space-Approximation Tradeoff for the Multi-Pass Streaming Set Cover Problem | 2017 | PODS | 5.7223891e-05 |
| 7,031 | Vertex and Hyperedge Connectivity in Dynamic Graph Streams | 2015 | PODS | 4.8561505e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 1,629 | Space-optimal Heavy Hitters with Strong Error Bounds | 2009 | PODS | 0.00011085267 |
| 2,752 | Composable Core-sets for Diversity and Coverage Maximization | 2014 | PODS | 8.1742326e-05 |
| 8,451 | Efficient framework for operating on data sketches | 2023 | VLDB | 4.5086031e-05 |
| 6,815 | Near-Optimal Algorithms for Shared Filter Evaluation in Data Stream Systems | 2008 | SIGMOD | 4.9177481e-05 |
| 11,329 | Estimation of the Size of Union of Delphic Sets: Achieving Independence from Stream Size | 2022 | PODS | 4.1945683e-05 |
| 11,321 | Approximately Counting Subgraphs in Data Streams | 2022 | PODS | 4.1945683e-05 |
| 11,442 | Estimating the Size of Union of Sets in Streaming Models | 2021 | PODS | 4.1945683e-05 |
| 11,167 | Set Cover in the One-pass Edge-arrival Streaming Model | 2023 | PODS | 4.1945683e-05 |
| 2,749 | Towards Tight Bounds for the Streaming Set Cover Problem | 2016 | PODS | 8.1773535e-05 |
| 5,066 | Tight Space-Approximation Tradeoff for the Multi-Pass Streaming Set Cover Problem | 2017 | PODS | 5.7223891e-05 |