Better streaming algorithms for the maximum coverage problem
From MaRDI portal
Recommendations
Cites work
- A 0.821-ratio purely combinatorial algorithm for maximum k-vertex cover in bipartite graphs
- A threshold of ln n for approximating set cover
- Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
- Chernoff–Hoeffding Bounds for Applications with Limited Independence
- Correlation clustering in data streams
- Densest subgraph in dynamic graph streams
- Fast algorithms for maximizing submodular functions
- scientific article; zbMATH DE number 6474901 (Why is no real title available?)
- scientific article; zbMATH DE number 6905172 (Why is no real title available?)
- scientific article; zbMATH DE number 1342117 (Why is no real title available?)
- scientific article; zbMATH DE number 7053292 (Why is no real title available?)
- Incidence geometries and the pass complexity of semi-streaming set cover
- Kernelization via Sampling with Applications to Finding Matchings and Related Problems in Dynamic Graph Streams
- Maximum matching in turnstile streams
- Maximum matchings in dynamic graph streams and the simultaneous communication model
- On Partial Vertex Cover and Budgeted Maximum Coverage Problems in Bipartite Graphs
- Online maximum \(k\)-coverage
- Pipage rounding: a new method of constructing algorithms with proven performance guarantee
- Randomized Distributed Edge Coloring via an Extension of the Chernoff--Hoeffding Bounds
- Robust lower bounds for communication and stream computation
- Semi-streaming set cover (extended abstract)
- Single pass spectral sparsification in dynamic streams
- Sketching cuts in graphs and hypergraphs
- Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams
- Spanners and sparsifiers in dynamic streams
- Spectral sparsification in dynamic graph streams
- Spectral sparsification of graphs
- Streaming algorithms for 2-coloring uniform hypergraphs
- Streaming algorithms for submodular function maximization
- The budgeted maximum coverage problem
- Tight bounds for single-pass streaming complexity of the set cover problem
Cited in
(15)- Almost-smooth histograms and sliding-window graph algorithms
- Online maximum \(k\)-coverage
- scientific article; zbMATH DE number 6905172 (Why is no real title available?)
- Tight bounds on the round complexity of the distributed maximum coverage problem
- Approximability of Monotone Submodular Function Maximization under Cardinality and Matroid Constraints in the Streaming Model
- Parameterized Streaming: Maximal Matching and Vertex Cover
- FPT-Algorithms for the \(\ell\) -Matchoid Problem with a Coverage Objective
- Robust algorithms under adversarial injections
- Fair maximization of monotone submodular functions in data streams
- Maximum unique coverage on streams: improved FPT approximation scheme and tighter space lower bound
- Submodular maximization subject to matroid intersection on the fly
- The one-way communication complexity of submodular maximization with applications to streaming and robustness
- Improved algorithms for maximum coverage in dynamic and random order streams
- Streaming submodular maximization with fairness constraints for massive data summarization
- On-line stream merging with max span and min coverage
This page was built for publication: Better streaming algorithms for the maximum coverage problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2322721)
