Deterministic streaming algorithms for non-monotone submodular maximization

Abstract

Submodular maximization is a significant area of interest in combinatorial optimization. It has various real-world applications. In recent years, streaming algorithms for submodular maximization have gained attention, allowing real-time processing of large data sets by examining each piece of data only once. However, most of the current state-of-the-art algorithms are only applicable to monotone submodular maximization. There are still significant gaps in the approximation ratios between monotone and non-monotone objective functions.

In this paper, we propose a streaming algorithm framework for non-monotone submodular maximization and use this framework to design deterministic streaming algorithms for the d-knapsack constraint and the knapsack constraint. Our 1-pass streaming algorithm for the d-knapsack constraint has a \frac{1}{4(d+1)}-ϵ approximation ratio, using \mathcal{O}\left(\frac{\tilde{B}\log \tilde{B}}{ϵ}\right) memory, and \mathcal{O}\left(\frac{\log \tilde{B}}{ϵ}\right) query time per element, where \tilde{B}=min(n,b) is the maximum number of elements that the knapsack can store. As a special case of the d-knapsack constraint, we have the 1-pass streaming algorithm with a 1/8-ϵ approximation ratio to the knapsack constraint. To our knowledge, there is currently no streaming algorithm for this constraint when the objective function is non-monotone, even when d = 1. In addition, we propose a multi-pass streaming algorithm with 1/6-ϵ approximation, which stores \mathcal{O}(\tilde{B}) elements.

Graphical abstract

Keywords

submodular maximization / streaming algorithms / cardinality constraint / knapsack constraint

Xiaoming Sun is a researcher at the Institute of Computing Technology, Chinese Academy of Sciences, China, leading the Laboratory for Quantum Computation and Theoretical Computer Science. His research interests include approximation algorithms, computational complexity, and quantum computing

Jialin Zhang is a researcher and a doctoral supervisor at the Institute of Computing Technology, Chinese Academy of Sciences, China. Her research topics include submodular optimization, approximation algorithms, online algorithms, quantum computing, and algorithmic game theory

Shuo Zhang is a doctoral student at the Institute of Computing Technology, Chinese Academy of Sciences, China, supervised by Professor Jialin Zhang. She mainly works on theoretical computers, algorithm design and optimization, particularly on the topic of submodular optimization

References

[1] Kempe D, Kleinberg J, Tardos É. Maximizing the spread of influence through a social network. In: Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2003, 137−146

[2] Das A, Kempe D. Algorithms for subset selection in linear regression. In: Proceedings of the 40th Annual ACM Symposium on Theory of Computing. 2008, 45−54

[3] Khanna R, Elenberg E R, Dimakis A G, Negahban S N, Ghosh J. Scalable greedy feature selection via weak submodularity. In: Proceedings of the 20th International Conference on Artificial Intelligence and Statistics. 2017, 1560−1568

[4] Iyer R, Bilmes J. Algorithms for approximate minimization of the difference between submodular functions, with applications. In: Proceedings of the 28th Conference on Uncertainty in Artificial Intelligence. 2012, 407−417

[5] Iyer R, Bilmes J. Submodular optimization with submodular cover and submodular knapsack constraints. In: Proceedings of the 26th International Conference on Neural Information Processing Systems. 2013, 2436−2444

[6] Jin L B, Zhang L, Zhao L . Max-difference maximization criterion: a feature selection method for text categorization. Frontiers of Computer Science, 2023, 17( 1): 171337

[7] Liang J, Zhang Y, Chen K, Qu B, Yu K, Yue C, Suganthan P N . An evolutionary multiobjective method based on dominance and decomposition for feature selection in classification. Science China Information Sciences, 2024, 67( 2): 120101

[8] Krause A, Guestrin C . Submodularity and its applications in optimized information gathering. ACM Transactions on Intelligent Systems and Technology, 2011, 2( 4): 32

[9] Nemhauser G L, Wolsey L A . Best algorithms for approximating the maximum of a submodular set function. Mathematics of Operations Research, 1978, 3( 3): 177–188

[10] Feige U . A threshold of ln n for approximating set cover. Journal of the ACM, 1998, 45( 4): 634–652

[11] Nemhauser G L, Wolsey L A, Fisher M L. An analysis of approximations for maximizing submodular set functions—I. Mathematical Programming, 1978, 14(1): 265−294

[12] Khuller S, Moss A, Naor J . The budgeted maximum coverage problem. Information Processing Letters, 1999, 70( 1): 39–45

[13] Sviridenko M . A note on maximizing a submodular set function subject to a knapsack constraint. Operations Research Letters, 2004, 32( 1): 41–43

[14] Vondrak J. Optimal approximation for the submodular welfare problem in the value oracle model. In: Proceedings of the 40th Annual ACM Symposium on Theory of Computing. 2008, 67−74

[15] Kulik A, Shachnai H, Tamir T. Maximizing submodular set functions subject to multiple linear constraints. In: Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms. 2009, 545−554

[16] Feldman M, Naor J, Schwartz R. A unified continuous greedy algorithm for submodular maximization. In: Proceedings of the 52nd IEEE Annual Symposium on Foundations of Computer Science. 2011, 570−579

[17] Buchbinder N, Feldman M. Deterministic algorithm and faster algorithm for submodular maximization subject to a matroid constraint. In: Proceedings of the 65th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2024. 2024

[18] Buchbinder N, Feldman M. Constrained submodular maximization via new bounds for DR-submodular functions. In: Proceedings of the 56th Annual ACM Symposium on Theory of Computing. 2024, 1820−1831

[19] Buchbinder N, Feldman M . Deterministic algorithms for submodular maximization problems. ACM Transactions on Algorithms, 2018, 14( 3): 32

[20] Sun X, Zhang J, Zhang S, Zhang Z. Improved deterministic algorithms for non-monotone submodular maximization. In: Proceedings of Computing and Combinatorics: 28th International Conference. 2022, 496−507

[21] Badanidiyuru A, Mirzasoleiman B, Karbasi A, Krause A. Streaming submodular maximization: massive data summarization on the fly. In: Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2014, 671−680

[22] Feldman M, Norouzi-Fard A, Svensson O, Zenklusen R. The one-way communication complexity of submodular maximization with applications to streaming and robustness. In: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing. 2020, 1363−1374

[23] Alaluf N, Ene A, Feldman M, Nguyen H L, Suh A . An optimal streaming algorithm for submodular maximization with a cardinality constraint. Mathematics of Operations Research, 2022, 47( 4): 2667–2690

[24] Huang C C, Kakimura N, Yoshida Y . Streaming algorithms for maximizing monotone submodular functions under a knapsack constraint. Algorithmica, 2020, 82( 4): 1006–1032

[25] Huang C C, Kakimura N . Improved streaming algorithms for maximizing monotone submodular functions under a knapsack constraint. Algorithmica, 2021, 83( 3): 879–902

[26] Huang C C, Kakimura N . Multi-pass streaming algorithms for monotone submodular function maximization. Theory of Computing Systems, 2022, 66( 1): 354–394

[27] Yaroslavtsev G, Zhou S, Avdiukhin D. “Bring your own greedy”+max: near-optimal 1/2-approximations for submodular knapsack. In: Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics. 2020, 3263−3274

[28] Kumar R, Moseley B, Vassilvitskii S, Vattani A . Fast greedy algorithms in mapReduce and streaming. ACM Transactions on Parallel Computing, 2015, 2( 3): 14

[29] Yu Q, Xu E L, Cui S. Submodular maximization with multi-knapsack constraints and its applications in scientific literature recommendations. In: Proceedings of 2016 IEEE Global Conference on Signal and Information Processing. 2016, 1295−1299

[30] Gupta A, Roth A, Schoenebeck G, Talwar K. Constrained non-monotone submodular maximization: offline and secretary algorithms. In: Proceedings of the 6th International Workshop on Internet and Network Economics. 2010, 246−257

[31] Lee J, Mirrokni V S, Nagarajan V, Sviridenko M . Maximizing nonmonotone submodular functions under matroid or knapsack constraints. SIAM Journal on Discrete Mathematics, 2010, 23( 4): 2053–2078

[32] Fadaei S, Fazli M A, Safari M A . Maximizing non-monotone submodular set functions subject to different constraints: combined algorithms. Operations Research Letters, 2011, 39( 6): 447–451

[33] Buchbinder N, Feldman M . Constrained submodular maximization via a nonsymmetric technique. Mathematics of Operations Research, 2019, 44( 3): 988–1005

[34] Sun X, Zhang J, Zhang S, Zhang Z . Improved deterministic algorithms for non-monotone submodular maximization. Theoretical Computer Science, 2024, 984: 114293

Acknowledgements

All author contributed equally to this paper and the order of author’s names is alphabetical. This work was supported in part by the National Natural Science Foundation of China (Grant Nos. 62325210 and 62272441).

Competing interests

Xiaoming Sun is an Editorial Board member of the journal and a co-author of this article. To minimize bias, they were excluded from all editorial decision-making related to the acceptance of this article for publication. The remaining authors declare no conflict of interest.

RIGHTS & PERMISSIONS

2025 Higher Education Press