Database Paper Browser

Back to papers

Set Cover in the One-pass Edge-arrival Streaming Model

Summary: Considers Set Cover in the one-pass edge-arrival streaming model (tuples (S,u)), capturing Dominating Set and strictly harder than set-arrival. Proves a strong adversarial vs random-order separation: adversarial streams need Õ(m) space for Õ(√n)-approx (lower bound), while random-order admits an Õ(√n)-approx with Õ(m/√n) space, and gives an adversarial α-approx tradeoff with space Õ((m n^2)/α^2). (summarized by gpt-5-mini on Feb 09 2026)

Paper ID
1897
Venue
PODS
Year
2023
Pagerank
4.1945683e-05
Overall Rank
11,167 | 22.32%
DOI
10.1145/3584372.3588678

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank Citing Paper Year Venue Pagerank
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 2 of 2 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
5,066 Tight Space-Approximation Tradeoff for the Multi-Pass Streaming Set Cover Problem 2017 PODS 5.7223891e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
11,332 The White-Box Adversarial Data Stream Model 2022 PODS 4.1945683e-05
4,403 A Framework for Adversarially Robust Streaming Algorithms 2020 PODS 6.2194225e-05
10,008 Representation Obliviousness and Pseudodeterminism in Streaming Algorithms 2026 PODS 4.1945683e-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
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
5,066 Tight Space-Approximation Tradeoff for the Multi-Pass Streaming Set Cover Problem 2017 PODS 5.7223891e-05