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

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

RIGHTS & PERMISSIONS

Higher Education Press