Research map / Learning theory and algorithms / Submodular and game algorithms
Submodular Optimization over Streams with Inhomogeneous Decays
Junzhou Zhao, Shuo Shang, Pinghui Wang, John C.S. Lui, Xiangliang Zhang
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use a histogram to maintain a selected subset of SieveStreaming instances instead of maintaining all instances | BasicStreaming on SSO-ID · SSO-ID | oracle calls | Improved |
| Use a histogram approximation rather than maintaining all instances | BasicStreaming on SSO-ID · SSO-ID | approximation factor: (1/2-ε) -> (1/3 - ε) | Hurt |
| Skip processing historical data and use compensation intervals to protect non-redundant instances | HistApprox on SSO-ID · SSO-ID | RAM requirement | Improved |
| Increase ε | HistStreaming · SSO-ID | oracle calls | Improved |
| Increase ε | HistStreaming · SSO-ID | solution quality | Hurt |
| Use HistStreaming instead of Greedy | maximum coverage on the evaluated datasets · SSO-ID, different budgets k | solution value ratio vs Greedy: larger than 80% | Mixed |
| Use HistStreaming instead of Greedy | maximum coverage on the evaluated datasets · SSO-ID, different budgets k | oracle call ratio vs Greedy: less than 10% | Improved |
Closest papers by meaning
- Do Less, Get More: Streaming Submodular Maximization with Subsampling (NeurIPS 2018 · similarity 0.90)
- Streaming k-Submodular Maximization under Noise subject to Size Constraint (ICML 2020 · similarity 0.90)
- Streaming Robust Submodular Maximization: A Partitioned Thresholding Approach (NeurIPS 2017 · similarity 0.90)
- Consistent Submodular Maximization (ICML 2024 · similarity 0.89)
- Learning-Augmented Dynamic Submodular Maximization (NeurIPS 2024 · similarity 0.86)
- Online and Streaming Algorithms for Constrained k-Submodular Maximization (AAAI 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.
