Beyond pointwise submodularity: non-monotone adaptive submodular maximization subject to knapsack and k-system constraints

DOI10.1016/J.TCS.2022.09.022OpenAlexW4300981391MaRDI QIDQ2087465FDOQ2087465

Authors: Shaojie Tang 

Publication date: 21 October 2022

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2104.04853

Recommendations

• Beyond pointwise submodularity: non-monotone adaptive submodular maximization subject to knapsack and \(k\)-system constraints
• Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack Constraint
• Beyond pointwise submodularity: non-monotone adaptive submodular maximization in linear time
• Non-monotone submodular maximization under matroid and knapsack constraints
• Maximizing nonmonotone submodular functions under matroid or knapsack constraints

zbMATH Keywords

approximation algorithmsnonmonotonicityadaptive submodularity

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• An analysis of approximations for maximizing submodular set functions—I
• Adaptive submodularity: theory and applications in active learning and stochastic optimization
• Maximising Real-Valued Submodular Functions: Primal and Dual Heuristics for Location Problems
• Price of dependence: stochastic submodular maximization with dependent items
• Influence maximization with partial feedback
• Beyond pointwise submodularity: non-monotone adaptive submodular maximization in linear time
• Robust Adaptive Submodular Maximization

Cited In (4)

• Non-monotone submodular function maximization under \(k\)-system constraint
• Data summarization beyond monotonicity: non-monotone two-stage submodular maximization
• Streaming adaptive submodular maximization
• Beyond pointwise submodularity: non-monotone adaptive submodular maximization subject to knapsack and \(k\)-system constraints

This page was built for publication: Beyond pointwise submodularity: non-monotone adaptive submodular maximization subject to knapsack and \(k\)-system constraints

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2087465)