Abstract: 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 ofmaximizingmonotone 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 $\frac{\gamma}{p+\gamma}$ for the former two problems, and $\frac{\xi \gamma}{p+\xi \gamma}$ for the last problem, which further has been improved to $\frac{\gamma}{p+\gamma}$, 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 $\frac{\xi}{p+\alpha \xi}$ for all the problems mentioned above, where α is the generalized curvature of set function. Finally, we show that our greedy algorithm does yield competitive practical performances using a variety of experiments on synthetic data.

Key words: Non-submodular function, p-matroid intersection, p-extendible system, p-system, Greedy algorithm