A Nearly-Linear Time Algorithm for Submodular Maximization with a Knapsack Constraint
From MaRDI portal
Publication:5091208
Recommendations
- Fast algorithms for maximizing submodular functions
- New approximations for monotone submodular maximization with knapsack constraint
- An almost optimal approximation algorithm for monotone submodular multiple knapsack
- Maximizing a monotone submodular function with a bounded curvature under a knapsack constraint
- Towards nearly-linear time algorithms for submodular maximization with a matroid constraint
Cites work
- A note on maximizing a submodular set function subject to a knapsack constraint
- Approximations for Monotone and Nonmonotone Submodular Maximization with Knapsack Constraints
- Fast algorithms for maximizing submodular functions
- Graph cuts with interacting edge weights: examples, approximations, and algorithms
- scientific article; zbMATH DE number 6474901 (Why is no real title available?)
- Maximising Real-Valued Submodular Functions: Primal and Dual Heuristics for Location Problems
- Maximizing a monotone submodular function with a bounded curvature under a knapsack constraint
- Near-optimal sensor placements in Gaussian processes: theory, efficient algorithms and empirical studies
- Revenue submodularity
- The budgeted maximum coverage problem
Cited in
(27)- Non-submodular streaming maximization with minimum memory and low adaptive complexity
- A refined analysis of submodular greedy
- An almost optimal approximation algorithm for monotone submodular multiple knapsack
- Multi-pass streaming algorithms for monotone submodular function maximization
- Maximum coverage with cluster constraints: an LP-based approximation technique
- On maximizing a monotone \(k\)-submodular function under a knapsack constraint
- A fast and deterministic algorithm for knapsack-constrained monotone DR-submodular maximization over an integer lattice
- On maximizing monotone or non-monotone k-submodular functions with the intersection of knapsack and matroid constraints
- Practical budgeted submodular maximization
- Efficient Submodular Function Maximization under Linear Packing Constraints
- Approximability of Monotone Submodular Function Maximization under Cardinality and Matroid Constraints in the Streaming Model
- Towards nearly-linear time algorithms for submodular maximization with a matroid constraint
- Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack Constraint
- Approximations for Monotone and Nonmonotone Submodular Maximization with Knapsack Constraints
- Monotone submodular maximization over the bounded integer lattice with cardinality constraints
- Submodular Maximization with Nearly-optimal Approximation and Adaptivity in Nearly-linear Time
- Budget-feasible mechanism design for non-monotone submodular objectives: offline and online
- Improved streaming algorithms for maximizing monotone submodular functions under a knapsack constraint
- Algorithms for cardinality-constrained monotone DR-submodular maximization with low adaptivity and query complexity
- Monotone \(k\)-submodular knapsack maximization: an analysis of the Greedy+Singleton algorithm
- Guarantees for maximization of \(k\)-submodular functions with a knapsack and a matroid constraint
- Budget-constrained profit maximization without non-negative objective assumption in social networks
- New approximations for monotone submodular maximization with knapsack constraint
- Subquadratic submodular maximization with a general matroid constraint
- Practical parallel algorithms for non-monotone submodular maximization
- Enhanced deterministic approximation algorithm for non-monotone submodular maximization under knapsack constraint with linear query complexity
- Streaming algorithms for maximizing k-submodular functions with the multi-knapsack constraint
This page was built for publication: A Nearly-Linear Time Algorithm for Submodular Maximization with a Knapsack Constraint
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5091208)
