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

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.

Streaming Algorithms for Non-Submodular Maximizationon the Integer Lattice

Many practical problems emphasize the importance of not only knowing whether an element is selectedbut also deciding to what extent it is selected,which imposes a challenge on submodule optimization.In this study,we consider the monotone,nondecreasing,and non-submodular maximization on the integer lattice with a cardinalityconstraint.We first design a two-pass streaming algorithm by refining the estimation interval of the optimal value.Foreach element,the algorithm not only decides whether to save the element but also gives the number of reservations.Then,we introduce the binary search as a subroutine to reduce the time complexity.Next,we obtain a one-passstreaming algorithm by dynamically updating the estimation interval of optimal value.Finally,we improve the memorycomplexity of this algorithm.

Minimizing Ratio of Monotone Non-submodular Functions

In this paper,we investigate the problem of minimizing the ratio of normalized non-negative monotone non-submodular set function f and normalized non-negative monotone set function g.We take advantage of the greedy technique and get a per-formance guarantee depending on the generalized curvature and inverse generalized curvature of f,as well as the submodularity ratio of g.Our results generalize the works of Bai et al.(Algorithms for optimizing the ratio of submodular functions.In:Proceedings of the 33rd International Conference on Machine L earning,2016)and Qian et al.(Optimizing ratio of monotone set functions.In:Proceedings of the 26th International Joint Conference on Artificial Intelligence,2017).