Greedy is Good:Constrained Non-submodular Function Maximization via Weak Submodularity  

作　　者：Ma-Jun Shi Wei Wang 

机构地区：[1]School of Statistics,Xi’an University of Finance and Economics,Xi’an,710100,Shaanxi,China [2]School of Mathematics and Statistics,Xi’an Jiaotong University,Xi’an,710049,Shaanxi,China

出　　处：《Journal of the Operations Research Society of China》2024年第3期627-648,共22页中国运筹学会会刊（英文）

基　　金：supported by the National Natural Science Foundation of China(No.11971376).

摘　　要：The widely used greedy algorithm has been recently shown to achieve near-optimal theoretical guarantees for the problems of constrained monotone non-submodular function maximization,with competitive performances in practice.In this paper,we investigate the problems of maximizing monotone non-submodular set functions under three classes of independent system constraints,including p-matroid intersection constraints,p-extendible system constraints and p-system constraints.We prove that the greedy algorithm yields an approximation ratio ofγ/p+γfor the former two problems,andξγ/p+ξγfor the last problem,which further has been improved toγ/p+γ,whereγ,ξdenote the submodularity ratio and the diminishing returns ratio of set function respectively.In addition,we also show that the greedy guarantees have a further refinement of for all the problems mentioned above,whereαis the generalized curvatureξ/p+αγof set function.Finally,we show that our greedy algorithm does yield competitive practical performances using a variety of experiments on synthetic data.

关 键 词：Non-submodular function p-matroid intersection p-extendible system P-SYSTEM Greedy algorithm 

分 类 号：O17[理学—数学]