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 pr...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.展开更多
基金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.
