Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack Constraint
From MaRDI portal
Publication:5094029
DOI10.1613/JAIR.1.13472OpenAlexW3105524178MaRDI QIDQ5094029FDOQ5094029
Authors: Georgios Amanatidis, Federico Fusco, Philip Lazos, Rebecca Reiffenhäuser, 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
Recommendations
- Beyond pointwise submodularity: non-monotone adaptive submodular maximization subject to knapsack and \(k\)-system constraints
- Beyond pointwise submodularity: non-monotone adaptive submodular maximization subject to knapsack and \(k\)-system constraints
- Non-monotone submodular maximization under matroid and knapsack constraints
- A Nearly-Linear Time Algorithm for Submodular Maximization with a Knapsack Constraint
- Maximizing nonmonotone submodular functions under matroid or knapsack constraints
Cites Work
- A threshold of ln n for approximating set cover
- Title not available (Why is that?)
- The budgeted maximum coverage problem
- An analysis of approximations for maximizing submodular set functions—I
- Submodular function maximization via the multilinear relaxation and contention resolution schemes
- Matroids and the greedy algorithm
- Near-optimal sensor placements in Gaussian processes: theory, efficient algorithms and empirical studies
- Title not available (Why is that?)
- Title not available (Why is that?)
- Maximizing Non-monotone Submodular Functions
- A note on maximizing a submodular set function subject to a knapsack constraint
- Maximizing non-monotone submodular set functions subject to different constraints: combined algorithms
- Approximations for Monotone and Nonmonotone Submodular Maximization with Knapsack Constraints
- Maximizing nonmonotone submodular functions under matroid or knapsack constraints
- Adaptive submodularity: theory and applications in active learning and stochastic optimization
- A Unified Continuous Greedy Algorithm for Submodular Maximization
- Maximising Real-Valued Submodular Functions: Primal and Dual Heuristics for Location Problems
- Streaming algorithms for submodular function maximization
- On the approximability of budget feasible mechanisms
- On multiplicative weight updates for concave and submodular function maximization
- Submodular maximization with cardinality constraints
- The submodular secretary problem goes linear
- Adaptivity gaps for stochastic probing: submodular and XOS functions
- A Nearly-Linear Time Algorithm for Submodular Maximization with a Knapsack Constraint
- An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation
- Approximate submodularity and its applications: subset selection, sparse approximation and dictionary selection
- The adaptive complexity of maximizing a submodular function
- Beyond pointwise submodularity: non-monotone adaptive submodular maximization in linear time
- Submodular maximization with nearly optimal approximation, adaptivity and query complexity
- Title not available (Why is that?)
- Submodular maximization with matroid and packing constraints in parallel
- Some properties of batch value of information in the selection problem
Cited In (6)
- An adaptive algorithm for maximization of non-submodular function with a matroid constraint
- Locally Adaptive Optimization: Adaptive Seeding for Monotone Submodular Functions
- Partial-monotone adaptive submodular maximization
- Partial-adaptive submodular maximization
- Beyond pointwise submodularity: non-monotone adaptive submodular maximization subject to knapsack and \(k\)-system constraints
- Improved deterministic algorithms for non-monotone submodular maximization
Uses Software
This page was built for publication: Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack Constraint
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5094029)
