Maximize an approximate k-submodular function under a knapsack constraint

DOI10.1007/978-981-96-4445-2_10MaRDI QIDQ6909251zbMATH OpenFDO

Authors Fanqing Meng, Qingqin Nong, Suning Gong, Xiaoying Qu

Publication date 29 October 2025

Full work available at URL https://doi.org/10.1007/978-981-96-4445-2_10

zbMATH Keywords

approximate \(k\)-submodular functiongreedy algorithmknapsack

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation methods and heuristics in mathematical programming (90C59)

Cites work

• A threshold of ln n for approximating set cover
• An efficient algorithm for image segmentation, Markov random fields and related problems
• Approximate Algorithms for the 0/1 Knapsack Problem
• Combinatorial optimization. Theory and algorithms
• scientific article; zbMATH DE number 3904328 (Why is no real title available?)
• scientific article; zbMATH DE number 1273005 (Why is no real title available?)
• Learning submodular functions
• Maximising Real-Valued Submodular Functions: Primal and Dual Heuristics for Location Problems
• Maximize a monotone function with a generic submodularity ratio
• Maximizing k-submodular functions and beyond
• Maximizing approximately non-k-submodular monotone set function with matroid constraint
• On maximizing a monotone \(k\)-submodular function subject to a matroid constraint
• On maximizing a monotone \(k\)-submodular function under a knapsack constraint
• Restricted strong convexity implies weak submodularity
• Submodular function minimization
• Submodular functions and electrical networks
• Submodular functions and optimization.
• Towards minimizing k-submodular functions
• Weakly \(k\)-submodular maximization under matroid constraint

This page was built for publication: Maximize an approximate \(k\)-submodular function under a knapsack constraint

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