Submodular + supermodular function maximization with knapsack constraint

DOI10.1016/J.DAM.2025.06.062MaRDI QIDQ6928012zbMATH OpenFDO

Authors Majun Shi, Zishen Yang, Wei Wang

Publication date 17 September 2025

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.DAM.2025.06.062

zbMATH Keywords

greedy algorithmiterated submodular+modular proceduresandwich methodsubmodular functionsupermodular function

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Cites work

• A note on maximizing a submodular set function subject to a knapsack constraint
• A tight analysis of the submodular-supermodular procedure
• An analysis of approximations for maximizing submodular set functions—I
• Greedy algorithm for maximization of non-submodular functions subject to knapsack constraint
• Greedy guarantees for non-submodular function maximization under independent system constraint with applications
• Greedy is good: constrained non-submodular function maximization via weak submodularity
• scientific article; zbMATH DE number 5888315 (Why is no real title available?)
• scientific article; zbMATH DE number 3635849 (Why is no real title available?)
• Interaction-aware influence maximization and iterated sandwich method
• Maximization problems of balancing submodular relevance and supermodular diversity
• Maximize a monotone function with a generic submodularity ratio
• Maximizing a monotone submodular function subject to a matroid constraint
• Maximizing a monotone submodular function with a bounded curvature under a knapsack constraint
• Maximizing a non-decreasing non-submodular function subject to various types of constraints
• Maximizing a Submodular Set Function Subject to a Matroid Constraint (Extended Abstract)
• Monotone submodular maximization over a matroid via non-oblivious local search
• Optimal approximation for submodular and supermodular optimization with bounded curvature
• Optimal approximation for the submodular welfare problem in the value oracle model
• Set function optimization
• Submodular set functions, matroids and the greedy algorithm: Tight worst- case bounds and some generalizations of the Rado-Edmonds theorem
• The budgeted maximum coverage problem
• Weak submodularity implies localizability: local search for constrained non-submodular function maximization

This page was built for publication: Submodular + supermodular function maximization with knapsack constraint

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