A Nearly-Linear Time Algorithm for Submodular Maximization with a Knapsack Constraint
From MaRDI portal
Publication:5091208
DOI10.4230/LIPIcs.ICALP.2019.53OpenAlexW2964501918MaRDI QIDQ5091208
No author found.
Publication date: 21 July 2022
Full work available at URL: https://arxiv.org/abs/1709.09767
Related Items (16)
Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack Constraint ⋮ 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 ⋮ 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 ⋮ On maximizing monotone or non-monotone \(k\)-submodular functions with the intersection of knapsack and matroid constraints ⋮ Practical budgeted submodular maximization ⋮ Non-submodular streaming maximization with minimum memory and low adaptive complexity ⋮ Monotone submodular maximization over the bounded integer lattice with cardinality constraints ⋮ Improved streaming algorithms for maximizing monotone submodular functions under a knapsack constraint ⋮ A refined analysis of submodular greedy ⋮ Multi-pass streaming algorithms for monotone submodular function maximization ⋮ Budget-Feasible Mechanism Design for Non-monotone Submodular Objectives: Offline and Online ⋮ Approximability of Monotone Submodular Function Maximization under Cardinality and Matroid Constraints in the Streaming Model ⋮ Maximum coverage with cluster constraints: an LP-based approximation technique
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Graph cuts with interacting edge weights: examples, approximations, and algorithms
- A note on maximizing a submodular set function subject to a knapsack constraint
- The budgeted maximum coverage problem
- Maximising Real-Valued Submodular Functions: Primal and Dual Heuristics for Location Problems
- Approximations for Monotone and Nonmonotone Submodular Maximization with Knapsack Constraints
- Maximizing a Monotone Submodular Function with a Bounded Curvature under a Knapsack Constraint
- Fast algorithms for maximizing submodular functions
This page was built for publication: A Nearly-Linear Time Algorithm for Submodular Maximization with a Knapsack Constraint
