An Optimal Streaming Algorithm for Submodular Maximization with a Cardinality Constraint
From MaRDI portal
Recommendations
- Streaming algorithms for submodular function maximization
- Improved streaming algorithms for maximizing monotone submodular functions under a knapsack constraint
- Streaming algorithms for maximizing monotone submodular functions under a knapsack constraint
- Improved streaming algorithms for maximizing monotone submodular functions under a knapsack constraint
- Streaming algorithms for maximizing monotone DR-submodular functions with a cardinality constraint on the integer lattice
Cites work
- scientific article; zbMATH DE number 3904328 (Why is no real title available?)
- scientific article; zbMATH DE number 3635849 (Why is no real title available?)
- A Unified Continuous Greedy Algorithm for Submodular Maximization
- An analysis of approximations for maximizing submodular set functions—I
- Best Algorithms for Approximating the Maximum of a Submodular Set Function
- Constrained submodular maximization via a nonsymmetric technique
- Deterministic (½ + ε)-Approximation for Submodular Maximization over a Matroid
- Deterministic Algorithms for Submodular Maximization Problems
- Maximizing Non-monotone Submodular Functions
- Maximizing a monotone submodular function subject to a matroid constraint
- Non-monotone submodular maximization under matroid and knapsack constraints
- Online Submodular Maximization with Free Disposal
- Online submodular maximization with preemption
- Online submodular welfare maximization: greedy beats 1/2 in random order
- Online submodular welfare maximization: greedy is optimal
- Randomized composable core-sets for distributed submodular maximization
- Streaming algorithms for submodular function maximization
- Submodular Max-SAT
- Submodular function maximization via the multilinear relaxation and contention resolution schemes
- Submodular maximization over multiple matroids via generalized exchange properties
- Submodular maximization with cardinality constraints
- Symmetry and approximability of submodular maximization problems
- The one-way communication complexity of submodular maximization with applications to streaming and robustness
Cited in
(19)- Streaming algorithms for robust submodular maximization
- An optimal streaming algorithm for non-submodular functions maximization on the integer lattice
- Thresholding Methods for Streaming Submodular Maximization with a Cardinality Constraint and Its Variants
- Approximability of Monotone Submodular Function Maximization under Cardinality and Matroid Constraints in the Streaming Model
- The one-way communication complexity of submodular maximization with applications to streaming and robustness
- Improved linear-time streaming algorithms for maximizing monotone cardinality-constrained set functions
- Non-submodular streaming maximization with minimum memory and low adaptive complexity
- Improved streaming algorithms for maximizing monotone submodular functions under a knapsack constraint
- Semi-streaming algorithms for submodular matroid intersection
- Semi-streaming algorithms for submodular matroid intersection
- Semi-Streaming Algorithms for Submodular Function Maximization Under b-Matching, Matroid, and Matchoid Constraints
- Non-submodular maximization on massive data streams
- Sequence submodular maximization meets streaming
- The power of subsampling in submodular maximization
- Streaming algorithms for submodular function maximization
- Approximation Algorithms for Non-Submodular Optimization Over Sliding Windows
- Bicriteria streaming algorithms to balance gain and cost with cardinality constraint
- The one-way communication complexity of submodular maximization with applications to streaming and robustness
- Streaming submodular maximization under \(d\)-knapsack constraints
This page was built for publication: An Optimal Streaming Algorithm for Submodular Maximization with a Cardinality Constraint
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5870351)
