Approximability of Monotone Submodular Function Maximization under Cardinality and Matroid Constraints in the Streaming Model
From MaRDI portal
Publication:5028360
Recommendations
- A linear-time streaming algorithm for cardinality-constrained maximizing monotone non-submodular set functions
- An Optimal Streaming Algorithm for Submodular Maximization with a Cardinality Constraint
- Streaming algorithms for maximizing monotone submodular functions under a knapsack constraint
- Streaming algorithms for maximizing monotone submodular functions under a knapsack constraint
- Multi-pass streaming algorithms for monotone submodular function maximization
- Streaming algorithms for maximizing monotone DR-submodular functions with a cardinality constraint on the integer lattice
- Improved 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 submodular function maximization
- Semi-Streaming Algorithms for Submodular Function Maximization Under b-Matching, Matroid, and Matchoid Constraints
Cites work
- scientific article; zbMATH DE number 6474901 (Why is no real title available?)
- scientific article; zbMATH DE number 3635849 (Why is no real title available?)
- A Nearly-Linear Time Algorithm for Submodular Maximization with a Knapsack Constraint
- A threshold of ln n for approximating set cover
- An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation
- An analysis of approximations for maximizing submodular set functions—I
- Best Algorithms for Approximating the Maximum of a Submodular Set Function
- Better streaming algorithms for the maximum coverage problem
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Fast algorithms for maximizing submodular functions
- Improved streaming algorithms for maximizing monotone submodular functions under a knapsack constraint
- Maximising Real-Valued Submodular Functions: Primal and Dual Heuristics for Location Problems
- Maximizing a monotone submodular function subject to a matroid constraint
- Maximizing a monotone submodular function with a bounded curvature under a knapsack constraint
- Maximizing submodular set functions subject to multiple linear constraints
- Monotone submodular maximization over a matroid via non-oblivious local search
- Multi-pass streaming algorithms for monotone submodular function maximization
- Near-optimal sensor placements in Gaussian processes: theory, efficient algorithms and empirical studies
- Online Submodular Maximization Problem with Vector Packing Constraint.
- Online submodular maximization with free disposal: randomization beats \(\frac{1}{4}\) for partition matroids
- Streaming algorithms for maximizing monotone submodular functions under a knapsack constraint
- Streaming algorithms for submodular function maximization
- Submodular Maximization with Nearly-optimal Approximation and Adaptivity in Nearly-linear Time
- Submodular function maximization in parallel via the multilinear relaxation
- Submodular function maximization via the multilinear relaxation and contention resolution schemes
- Submodular maximization over multiple matroids via generalized exchange properties
- Symmetry and approximability of submodular maximization problems
- The adaptive complexity of maximizing a submodular function
- The one-way communication complexity of submodular maximization with applications to streaming and robustness
- Towards nearly-linear time algorithms for submodular maximization with a matroid constraint
Cited in
(8)- Improved linear-time streaming algorithms for maximizing monotone cardinality-constrained set functions
- On maximizing monotone or non-monotone \(k\)-submodular functions with the intersection of knapsack and matroid constraints
- Semi-streaming algorithms for submodular matroid intersection
- Thresholding Methods for Streaming Submodular Maximization with a Cardinality Constraint and Its Variants
- Semi-Streaming Algorithms for Submodular Function Maximization Under b-Matching, Matroid, and Matchoid Constraints
- FPT-Algorithms for the \(\ell\) -Matchoid Problem with a Coverage Objective
- Multi-pass streaming algorithms for monotone submodular function maximization
- Guarantees for maximization of \(k\)-submodular functions with a knapsack and a matroid constraint
This page was built for publication: Approximability of Monotone Submodular Function Maximization under Cardinality and Matroid Constraints in the Streaming Model
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5028360)
