Many practical applications impose challenges of selecting required elements from a vast amount of data, with the requirement of maximizing non-submodular set functions. In this paper, we design two algorithms for the problem of maximizing a normalized monotone non-submodular set function with a cardinality constraint. By utilizing the concept of a diminishing-return ratio, we first propose a one-pass algorithm called Non-SubModular-Sieve-Streaming$ ^{++} $, attaining an approximation ratio of $ \min\left\{(1-\varepsilon)\gamma/2^\gamma, 1-1/2^\gamma\right \} $, where $ \varepsilon\in (0, 1) $ is any small real number and $ \gamma\in(0, 1] $ is the diminishing return ratio. Then, to reduce the adaptive complexity, we improve the algorithm and derive Non-SubModular-Batch-Sieve-Streaming$ ^{++} $ with an approximation ratio $ \min\left\{(1-3\varepsilon)\gamma/2^\gamma, 1-1/2^\gamma\right \} $ for any $ \varepsilon\in (0, 1/3) $. Finally, numerical experiments are carried out to evaluate the effectiveness and feasibility of the two Streaming algorithms.
Citation: Meixia Li, Jiansheng Cai, Jingjing Tan, Wenchao Wang, Xueling Zhou. Streaming non-submodular maximization subject to a cardinality constraint[J]. AIMS Mathematics, 2026, 11(10): 32973-32991. doi: 10.3934/math.20261293
Many practical applications impose challenges of selecting required elements from a vast amount of data, with the requirement of maximizing non-submodular set functions. In this paper, we design two algorithms for the problem of maximizing a normalized monotone non-submodular set function with a cardinality constraint. By utilizing the concept of a diminishing-return ratio, we first propose a one-pass algorithm called Non-SubModular-Sieve-Streaming$ ^{++} $, attaining an approximation ratio of $ \min\left\{(1-\varepsilon)\gamma/2^\gamma, 1-1/2^\gamma\right \} $, where $ \varepsilon\in (0, 1) $ is any small real number and $ \gamma\in(0, 1] $ is the diminishing return ratio. Then, to reduce the adaptive complexity, we improve the algorithm and derive Non-SubModular-Batch-Sieve-Streaming$ ^{++} $ with an approximation ratio $ \min\left\{(1-3\varepsilon)\gamma/2^\gamma, 1-1/2^\gamma\right \} $ for any $ \varepsilon\in (0, 1/3) $. Finally, numerical experiments are carried out to evaluate the effectiveness and feasibility of the two Streaming algorithms.
| [1] | N. Lawrence, M. Seeger, R. Herbrich, Fast sparse Gaussian process methods: The informative vector machine, in Advances in Neural Information Processing Systems 15 (NIPS 2002), 2003,625–632. |
| [2] | A. Krause, A. Singh, C. Guestrin, Near-optimal sensor placements in Gaussian processes: Theory, efficient algorithms and empirical studies, J. Mach. Learn. Res., 9 (2008), 235–284. |
| [3] | M. Ajtai, T. S. Jayram, R. Kumar, D. Sivakumar, Approximate counting of inversions in a data stream, in Proceedings of the 34th ACM Symposium on Theory of Computing (STOC), 2002,370–379. |
| [4] | D. Dueck, B. J. Frey, Non-metric affinity propagation for unsupervised image categorization, in Proceedings of the IEEE International Conference on Computer Vision (ICCV), 2007, 1–8. |
| [5] | K. El-Arini, C. Guestrin, Beyond keyword search: Discovering relevant scientific literature, in Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), 2011,439–447. |
| [6] | K. El-Arini, G. Veda, D. Shahaf, C. Guestrin, Turning down the noise in the blogosphere, in Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), 2009,289–298. |
| [7] | R. Gomes, A. Krause, Budgeted nonparametric learning from data streams, in Proceedings of the International Conference on Machine Learning (ICML), 2010,391–398. |
| [8] | S. Guha, N. Mishra, R. Motwani, L. O'Callaghan, Clustering data streams, in Proceedings of the 41st IEEE Symposium on Foundations of Computer Science (FOCS), 2000,359–366. |
| [9] | C. Reed, Z. Ghahramani, Scaling the Indian buffet process via submodular maximization, in Proceedings of the 30th International Conference on Machine Learning (ICML), PMLR 28, 2013, 1013–1021. Available from: https://proceedings.mlr.press/v28/reed13.html |
| [10] |
D. Du, Y. Li, N. Xiu, D. Xu, Simultaneous approximation of multi-criteria submodular function maximization, J. Oper. Res. Soc. China, 2 (2014), 271–290. https://doi.org/10.1007/s40305-014-0053-z doi: 10.1007/s40305-014-0053-z
|
| [11] |
B. Goldengorin, D. Ghosh, A multilevel search algorithm for the maximization of submodular functions applied to the quadratic cost partition problem, J. Global Optim., 32 (2005), 65–82. https://doi.org/10.1007/s10898-004-5909-z doi: 10.1007/s10898-004-5909-z
|
| [12] | A. Krause, D. Golovin, Submodular function maximization, in Tractability: Practical Approaches to Hard Problems, Cambridge University Press, Cambridge, 2014, 71–104. https://doi.org/10.1017/CBO9781139177801.004 |
| [13] | A. Das, D. Kempe, Submodular meets spectral: Greedy algorithms for subset selection, sparse approximation and dictionary selection, in Proceedings of the International Conference on Machine Learning (ICML), 2011, 1057–1064. |
| [14] | E. Elenberg, A. G. Dimakis, M. Feldman, A. Karbasi, Streaming weak submodularity: Interpreting neural networks on the fly, in Advances in Neural Information Processing Systems 30 (NeurIPS 2017), 2017, 4044–4054. |
| [15] |
Y. Wang, D. Xu, Y. Wang, D. Zhang, Non-submodular maximization on massive data streams, J. Global Optim., 76 (2020), 729–743. https://doi.org/10.1007/s10898-019-00840-8 doi: 10.1007/s10898-019-00840-8
|
| [16] | A. Breuer, E. Balkanski, Y. Singer, The FAST algorithm for submodular maximization, arXiv: 1907.06173 (2019). |
| [17] | E. Balkanski, A. Rubinstein, Y. Singer, An exponential speedup in parallel running time for submodular maximization without loss in approximation, in Proceedings of the 30th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2019,283–302. |
| [18] |
U. Feige, A threshold of $\ln n$ for approximating set cover, J. ACM, 45 (1998), 634–652. https://doi.org/10.1145/285055.285059 doi: 10.1145/285055.285059
|
| [19] |
G. L. Nemhauser, L. A. Wolsey, M. L. Fisher, An analysis of approximations for maximizing submodular set functions—I, Math. Program., 14 (1978), 265–294. https://doi.org/10.1007/BF01588971 doi: 10.1007/BF01588971
|
| [20] | A. Badanidiyuru, J. Vondrák, Fast algorithms for maximizing submodular functions, in Proceedings of the 25th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2014, 1497–1514. |
| [21] | A. Ene, H. Nguyen, A nearly-linear time algorithm for submodular maximization with a knapsack constraint, in Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP), 2019, 53: 1–53: 12. |
| [22] |
A. Kulik, H. Shachnai, T. Tamir, Approximations for monotone and nonmonotone submodular maximization with knapsack constraints, Math. Oper. Res., 38 (2013), 729–739. https://doi.org/10.1287/moor.2013.0592 doi: 10.1287/moor.2013.0592
|
| [23] |
M. Sviridenko, A note on maximizing a submodular set function subject to a knapsack constraint, Oper. Res. Lett., 32 (2004), 41–43. https://doi.org/10.1016/S0167-6377(03)00062-2 doi: 10.1016/S0167-6377(03)00062-2
|
| [24] | N. Buchbinder, M. Feldman, M. Garg, Deterministic $(\frac{1}{2})+\varepsilon$-approximation for submodular maximization over a matroid, in Proceedings of the 30th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2019,241–254. |
| [25] |
Y. Filmus, J. Ward, Monotone submodular maximization over a matroid via non-oblivious local search, SIAM J. Comput., 43 (2014), 514–542. https://doi.org/10.1137/130920277 doi: 10.1137/130920277
|
| [26] | J. Vondrák, Optimal approximation for the submodular welfare problem in the value oracle model, in Proceedings of the 40th ACM Symposium on Theory of Computing (STOC), 2008, 67–74. |
| [27] | A. Badanidiyuru, B. Mirzasoleiman, A. Karbasi, A. Krause, Streaming submodular maximization: Massive data summarization on the fly, in Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), 2014,671–680. |
| [28] | N. Buchbinder, M. Feldman, R. Schwartz, Online submodular maximization with preemption, in Proceedings of the 26th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2015, 1202–1216. |
| [29] | E. Kazemi, M. Mitrović, M. Zadimoghaddam, S. Lattanzi, A. Karbasi, Submodular streaming in all its glory: Tight approximation, minimum memory and low adaptive complexity, in Proceedings of the 36th International Conference on Machine Learning (ICML), PMLR 97, 2019, 3311–3320. |
| [30] | J. Tan, R. Yang, Y. Zhang, M. Zhu, Streaming algorithms for non-submodular functions maximization with $d$-knapsack constraint on the integer lattice, Asia-Pac. J. Oper. Res., 40 (2023), Article ID 107766 (16 pages). https://doi.org/10.1142/S0217595923400183 |
| [31] |
X. Zhao, M. Li, B. Qu, CQ-like algorithm for nonconvex split feasibility problem with multiple output sets, Asia-Pac. J. Oper. Res., 43 (2026), 1–28. https://doi.org/10.1142/S0217595925500289 doi: 10.1142/S0217595925500289
|
| [32] |
X. Zhao, M. Li, B. Qu, Inertial alternating projection gradient algorithm for nonconvex split feasibility problem with multiple output sets, J. Ind. Manag. Optim., 21 (2025), 6190–6218. https://doi.org/10.3934/jimo.2025128 doi: 10.3934/jimo.2025128
|
| [33] | M. Feldman, A. Karbasi, E. Kazemi, Do less, get more: Streaming submodular maximization with subsampling, in Advances in Neural Information Processing Systems 31 (NeurIPS 2018), 2018,730–740. |
| [34] | B. Mirzasoleiman, S. Jegelka, A. Krause, Streaming non-monotone submodular maximization: Personalized video summarization on the fly, arXiv: 1706.03583 (2018). |
| [35] |
K. Chaloner, I. Verdinelli, Bayesian experimental design: A review, Stat. Sci., 10 (1995), 273–304. https://doi.org/10.1214/ss/1177009939 doi: 10.1214/ss/1177009939
|
| [36] | A. A. Bian, J. M. Buhmann, A. Krause, S. Tschiatschek, Guarantees for greedy maximization of non-submodular functions with applications, in Proceedings of the 34th International Conference on Machine Learning (ICML), PMLR 70, 2017,498–507. Available from: https://proceedings.mlr.press/v70/bian17a.html |
Figures(3) / Tables(1)
Meixia Li, Jiansheng Cai, Jingjing Tan, Wenchao Wang, Xueling Zhou. Streaming non-submodular maximization subject to a cardinality constraint[J]. AIMS Mathematics, 2026, 11(10): 32973-32991. doi: 10.3934/math.20261293
DownLoad: