Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack Constraint

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

zbMATH Keywords

uncertaintymachine learning

Mathematics Subject Classification ID

Artificial intelligence (68Txx)

Related Items (3)

Improved deterministic algorithms for non-monotone submodular maximization ⋮ Partial-adaptive submodular maximization ⋮ Partial-monotone adaptive submodular maximization

Uses Software

• MovieLens

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