Tight Space-Approximation Tradeoff for the Multi-Pass Streaming Set Cover Problem

Summary: Shows any α-approx streaming set-cover algorithm requires Ω(m n^{1/α}) space even with polylog(n) passes and random-order streams, matching Har-Peled et al.'s O(α)-pass upper bound. Also gives tight lower bounds for (1−ε)-approx streaming maximum coverage, settling the space complexity. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1728
Venue: PODS
Year: 2017
Pagerank: 5.716891e-05
Overall Rank: 5,064 | 64.81%
DOI: 10.1145/3034786.3056116

Incoming Non-self Citations Over Time

Authors

1. Sepehr Assadi

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
7,146	Tight Trade-offs for the Maximum k-Coverage Problem in the General Streaming Model	2019	PODS	4.8133378e-05
11,170	Set Cover in the One-pass Edge-arrival Streaming Model	2023	PODS	4.1905499e-05

Outgoing Citations (Sorted by Pagerank)

Showing 1 of 1 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
2,755	Towards Tight Bounds for the Streaming Set Cover Problem	2016	PODS	8.1694565e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
1,117	Tight Bounds for Lp Samplers, Finding Duplicates in Streams, and Related Problems	2011	PODS	0.0001386123
4,399	A Framework for Adversarially Robust Streaming Algorithms	2020	PODS	6.2134435e-05
2,756	Composable Core-sets for Diversity and Coverage Maximization	2014	PODS	8.1682323e-05
6,813	Near-Optimal Algorithms for Shared Filter Evaluation in Data Stream Systems	2008	SIGMOD	4.9135157e-05
11,323	Approximately Counting Subgraphs in Data Streams	2022	PODS	4.1905499e-05
11,331	Estimation of the Size of Union of Delphic Sets: Achieving Independence from Stream Size	2022	PODS	4.1905499e-05
11,445	Estimating the Size of Union of Sets in Streaming Models	2021	PODS	4.1905499e-05
11,170	Set Cover in the One-pass Edge-arrival Streaming Model	2023	PODS	4.1905499e-05
7,146	Tight Trade-offs for the Maximum k-Coverage Problem in the General Streaming Model	2019	PODS	4.8133378e-05
2,755	Towards Tight Bounds for the Streaming Set Cover Problem	2016	PODS	8.1694565e-05