Submodular maximization under knapsack and partition matroid constraints

DOI10.1007/S10878-026-01470-ZMaRDI QIDQ7406193zbMATH OpenFDO

Authors Dongkai Xu, Jianhua Yuan, Zhongzheng Tang

Publication date 2026

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/S10878-026-01470-Z

zbMATH Keywords

approximation guaranteegreedy algorithmknapsack constraintpartition matroidsubmodular maximization

Mathematics Subject Classification ID

Mathematical programming (90Cxx)

Cites work

• A note on maximizing a submodular set function subject to a knapsack constraint
• A refined analysis of submodular greedy
• A threshold of ln n for approximating set cover
• An 0. 828-approximation algorithm for the uncapacitated facility location problem
• An analysis of approximations for maximizing submodular set functions—I
• An Exact Algorithm for Maximum Entropy Sampling
• Constrained submodular maximization via greedy local search
• Fast algorithms for maximizing submodular functions
• scientific article; zbMATH DE number 3635849 (Why is no real title available?)
• Maximising Real-Valued Submodular Functions: Primal and Dual Heuristics for Location Problems
• Modified greedy algorithm for monotone submodular maximization with knapsack and partition matroid constraints
• Practical budgeted submodular maximization
• The budgeted maximum coverage problem

This page was built for publication: Submodular maximization under knapsack and partition matroid constraints

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