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.7223891e-05
Overall Rank: 5,066 | 64.76%
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,145	Tight Trade-offs for the Maximum k-Coverage Problem in the General Streaming Model	2019	PODS	4.8179617e-05
11,167	Set Cover in the One-pass Edge-arrival Streaming Model	2023	PODS	4.1945683e-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,749	Towards Tight Bounds for the Streaming Set Cover Problem	2016	PODS	8.1773535e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
1,094	Tight Bounds for Lp Samplers, Finding Duplicates in Streams, and Related Problems	2011	PODS	0.00014129658
4,403	A Framework for Adversarially Robust Streaming Algorithms	2020	PODS	6.2194225e-05
2,752	Composable Core-sets for Diversity and Coverage Maximization	2014	PODS	8.1742326e-05
6,815	Near-Optimal Algorithms for Shared Filter Evaluation in Data Stream Systems	2008	SIGMOD	4.9177481e-05
11,321	Approximately Counting Subgraphs in Data Streams	2022	PODS	4.1945683e-05
11,329	Estimation of the Size of Union of Delphic Sets: Achieving Independence from Stream Size	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
7,145	Tight Trade-offs for the Maximum k-Coverage Problem in the General Streaming Model	2019	PODS	4.8179617e-05
2,749	Towards Tight Bounds for the Streaming Set Cover Problem	2016	PODS	8.1773535e-05