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.
[1] Fujishige, S.: Submodular Functions and Optimization. Elsevier Science, Amsterdan (2005)
[2] Nemhauser, G.L., Wolsey, L.A., Fisher, M.L.: An analysis of approximations for maximizing submodular set functions-I. Math. Program. 14(1), 265-294(1978)
[3] Fisher, M.L., Nemhauser, G.L., Wolsey, L.A.: An analysis of approximations for maximizing submodular set functions-II. Math. Prog. Study 8, 73-87(1978)
[4] Calinescu, G., Chekuri, C., Pál, M., Vondrák, J.: Maximizing a monotone submodular function subject to a matroid constraint. SIAM J. Comput. 40(6), 1740-1766(2011)
[5] Calinescu, G., Chekuri, C., Pál, M., Vondrák, J.: Maximizing a submodular set function subject to a matroid constraint (extended abstract). In: Proc. the 12th conference on integer programming and combinatorial optimization, 4513:182-196(2007)
[6] Vondrák, J.: Optimal approximation for the submodular welfare problem in the value oracle model. In: Proc. the 40th ACM Symp. on theory of computing, pp.67-74(2008)
[7] Filmus, Y., Ward, J.: Monotone submodular maximization over a matroid via non-oblivious local search. SIAM J. Comput. 43(2), 514-542(2013)
[8] Das, A., Kempe, D.: Submodularmeets spectral: greedy algorithmsfor subset selection, sparse approximation and dictionary selection. In: Proc. the 28th international conference on machine learning, pp.1057-1064(2011)
[9] Elenberg, E.R., Khanna, R., Dimakis, A.G., Negahban, S.: Restricted strong convexity implies weak submodularity. Ann. Stat. 46(6B), 3539-3568(2016)
[10] Bian, A.A., Buhmann, J.M., Krause, A., Tschiatschek, S.: Guarantees for greedy maximization of non-submodular functions with applications. In: Proc. the 34th international conference on machine learning, pp.498-507(2017)
[11] Gatmiry, K., Rodriguez, M.G.: Non-submodular function maximization subject to a matroid constraint, with applications. arXiv preprint arXiv:1811.07863v4(2018)
[12] Chen, L., Feldman, M., Karbasi, A.:Weakly submodularmaximization beyond cardinality constraints: does randomization help greedy?. In: Proc. the 35th international conference on machine learning, pp.804-813(2018)
[13] Gong, S., Nong, Q., Liu, W., Fang, Q.: Parametric monotone function maximization with matroid constraints. J. Global Optim. 75(3), 833-849(2019)
[14] Nong, Q., Sun, T., Gong, S., Fang, Q., Du, D., Shao, X.: Maximize a monotone function with a generic submodularity ratio. Theory Comput. Sci. 853, 16-24(2021)
[15] Wang, Y.J., Du, D.L., Jiang, Y.J., Zhang, X.Z.: Non-submodular maximization with matroid and knapsack constraints. Asia-Pacific J. Oper. Res. 38(05), 2140001(2021)
[16] Wang, Y.J., Xu, D.C., Wang, Y.S., Zhang, D.M.: Non-submodular maximization on massive data streams. J. Global Optim. 76, 729-743(2020)
[17] Feldman, M., Izsak, R.: Constrained monotone function maximization and the supermodular degree. arXiv preprint arXiv:1407.6328(2014)
[18] Conforti, M., Cornuéjols, G.: Submodular functions, matroids and the greedy algorithm: tight worstcase bounds and some generalizations of the Rado-Edmonds theorem. Discret. Appl. Math. 7(3), 251-274(1984)
[19] Krause, A., Singh, A., Guestrin, C.: Near-optimal sensor placements in gaussian processes: theory, efficient algorithms and empirical studies. J. Mach. Learn. Res. 9, 235-284(2008)
[20] Qian, C., Yu, Y., Tang, K.: Approximation guarantees of stochastic greedy algorithms for subset selection. In: Proc. the 27th international joint conference on artificial intelligence (2018)
[21] Du, D.Z., Ko, K.I., Hu, X.D.: Design and Analysis of Approximation Algorithms. Springer, New York (2012)
[22] Vondrák, J.: Submodularity and curvature: the optimal algorithm. RIMS Kokyuroku Bessatsu B23, 253-266(2009)
[23] Sviridenko, M., Vondrák, J., Ward, J.: Optimal approximation for submodular and supermodular optimization with bounded curvature. In: Proc. the 26th ACM-SIAM Symp. on discrete algorithms, pp.1134-1148(2015)
