Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack Constraint
From MaRDI portal
Publication:5094029
DOI10.1613/jair.1.13472OpenAlexW3105524178MaRDI QIDQ5094029
Rebecca Reiffenhäuser, Philip Lazos, Federico Fusco, Georgios Amanatidis, Stefano Leonardi
Publication date: 2 August 2022
Published in: Journal of Artificial Intelligence Research (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2007.05014
Related Items (3)
Improved deterministic algorithms for non-monotone submodular maximization ⋮ Partial-adaptive submodular maximization ⋮ Partial-monotone adaptive submodular maximization
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Maximizing non-monotone submodular set functions subject to different constraints: combined algorithms
- A note on maximizing a submodular set function subject to a knapsack constraint
- The budgeted maximum coverage problem
- Beyond pointwise submodularity: non-monotone adaptive submodular maximization in linear time
- Some Properties of Batch Value of Information in the Selection Problem
- On Multiplicative Weight Updates for Concave and Submodular Function Maximization
- Maximizing Nonmonotone Submodular Functions under Matroid or Knapsack Constraints
- Maximizing Non-monotone Submodular Functions
- A threshold of ln n for approximating set cover
- Streaming Algorithms for Submodular Function Maximization
- Maximising Real-Valued Submodular Functions: Primal and Dual Heuristics for Location Problems
- An analysis of approximations for maximizing submodular set functions—I
- Adaptivity Gaps for Stochastic Probing: Submodular and XOS Functions
- The Submodular Secretary Problem Goes Linear
- A Nearly-Linear Time Algorithm for Submodular Maximization with a Knapsack Constraint
- Submodular Function Maximization via the Multilinear Relaxation and Contention Resolution Schemes
- Approximations for Monotone and Nonmonotone Submodular Maximization with Knapsack Constraints
- Submodular maximization with matroid and packing constraints in parallel
- The adaptive complexity of maximizing a submodular function
- Submodular Maximization with Nearly Optimal Approximation, Adaptivity and Query Complexity
- An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation
- Submodular Maximization with Cardinality Constraints
- A Unified Continuous Greedy Algorithm for Submodular Maximization
- Matroids and the greedy algorithm
This page was built for publication: Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack Constraint