Non-submodular streaming maximization with minimum memory and low adaptive complexity
From MaRDI portal
Publication:2039664
DOI10.1007/978-3-030-57602-8_20zbMATH Open1485.90112OpenAlexW3048291236MaRDI QIDQ2039664FDOQ2039664
Authors: Meixia Li, Xueling Zhou, Jingjing Tan, Wenchao Wang 
Publication date: 5 July 2021
Full work available at URL: https://doi.org/10.1007/978-3-030-57602-8_20
Recommendations
- Non-submodular maximization on massive data streams
- An Optimal Streaming Algorithm for Submodular Maximization with a Cardinality Constraint
- An optimal streaming algorithm for non-submodular functions maximization on the integer lattice
- Streaming algorithms for submodular function maximization
- Approximation Algorithms for Non-Submodular Optimization Over Sliding Windows
Cites Work
- A threshold of ln n for approximating set cover
- Monotone submodular maximization over a matroid via non-oblivious local search
- Data Streams: Algorithms and Applications
- An analysis of approximations for maximizing submodular set functions—I
- Fast algorithms for maximizing submodular functions
- Near-optimal sensor placements in Gaussian processes: theory, efficient algorithms and empirical studies
- A note on maximizing a submodular set function subject to a knapsack constraint
- A multilevel search algorithm for the maximization of submodular functions applied to the quadratic cost partition problem
- Optimal approximation for the submodular welfare problem in the value oracle model
- Approximations for Monotone and Nonmonotone Submodular Maximization with Knapsack Constraints
- Simultaneous approximation of multi-criteria submodular function maximization
- Approximate counting of inversions in a data stream
- Deterministic (½ + ε)-Approximation for Submodular Maximization over a Matroid
- Streaming algorithms for submodular function maximization
- Online submodular maximization with preemption
- Non-submodular maximization on massive data streams
- Online submodular maximization with free disposal: randomization beats \(\frac{1}{4}\) for partition matroids
- A Nearly-Linear Time Algorithm for Submodular Maximization with a Knapsack Constraint
- An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation
Cited In (5)
- Improved linear-time streaming algorithms for maximizing monotone cardinality-constrained set functions
- A linear-time streaming algorithm for cardinality-constrained maximizing monotone non-submodular set functions
- Title not available (Why is that?)
- Non-submodular maximization on massive data streams
- Fast algorithms for maximizing monotone nonsubmodular functions
This page was built for publication: Non-submodular streaming maximization with minimum memory and low adaptive complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2039664)
