Deterministic streaming algorithms for non-monotone submodular maximization

doi:10.1007/s11704-024-40266-4

Frontiers of Computer Science

2025, Vol. 19

Issue (6): 196404 https://doi.org/10.1007/s11704-024-40266-4

本期目录

Deterministic streaming algorithms for non-monotone submodular maximization

Xiaoming SUN^1,², Jialin ZHANG^1,², Shuo ZHANG^1,²(

)

¹. State Key Lab of Processors, Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100190, China
². School of Computer Science and Technology, University of Chinese Academy of Sciences, Beijing 100049, China

全文: PDF(1672 KB) HTML

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 $1 4 (d + 1) − ϵ$ approximation ratio, using $O (B ~ log ⁡ B ~ ϵ)$ memory, and $O (log ⁡ B ~ ϵ)$ query time per element, where $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 $O (B ~)$ elements.

Key words： submodular maximization streaming algorithms cardinality constraint knapsack constraint

收稿日期: 2024-03-25 出版日期: 2024-10-28

Corresponding Author(s): Shuo ZHANG

引用本文:

. [J]. Frontiers of Computer Science, 2025, 19(6): 196404.
Xiaoming SUN, Jialin ZHANG, Shuo ZHANG. Deterministic streaming algorithms for non-monotone submodular maximization. Front. Comput. Sci., 2025, 19(6): 196404.

链接本文:

https://academic.hep.com.cn/fcs/CN/10.1007/s11704-024-40266-4
https://academic.hep.com.cn/fcs/CN/Y2025/V19/I6/196404

Constraint	Reference	Ratio	Pass	Memory	Monotonicity
d-knapsack	[28]	$1 2 d + 1 ? ?$	1	$O (B ~ ? ? 1 log ? B ~)$	Monotone
d-knapsack	Theorem 6	$1 4 (d + 1) ? ?$	1	$O (B ~ ? ? 1 log ? B ~)$	Non-monotone
Knapsack	[25]	$2 / 5 ? ?$	1	$O (B ~ ? ? 4 log 4 ? B ~)$	Monotone
Knapsack	[27]	$1 / 2 ? ?$	$O (1 / ?)$	$O (B ~ ? ? 1 log ? B ~)$	Monotone
Knapsack	Theorem 6	$1 / 8 ? ?$	1	$O (B ~ ? ? 1 log ? B ~)$	Non-monotone
Knapsack	Theorem 8	$1 / 6 ? ?$	$O (log ? b / ?)$	$O (B ~)$	Non-monotone

Tab.1

1	D, Kempe J, Kleinberg É 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	A, Das D Kempe . Algorithms for subset selection in linear regression. In: Proceedings of the 40th Annual ACM Symposium on Theory of Computing. 2008, 45−54
3	R, Khanna E R, Elenberg A G, Dimakis S N, Negahban J Ghosh . Scalable greedy feature selection via weak submodularity. In: Proceedings of the 20th International Conference on Artificial Intelligence and Statistics. 2017, 1560−1568
4	R, Iyer J Bilmes . 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	R, Iyer J Bilmes . 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	L B, Jin L, Zhang L Zhao . Max-difference maximization criterion: a feature selection method for text categorization. Frontiers of Computer Science, 2023, 17( 1): 171337
7	J, Liang Y, Zhang K, Chen B, Qu K, Yu C, Yue P N Suganthan . An evolutionary multiobjective method based on dominance and decomposition for feature selection in classification. Science China Information Sciences, 2024, 67( 2): 120101
8	A, Krause C Guestrin . Submodularity and its applications in optimized information gathering. ACM Transactions on Intelligent Systems and Technology, 2011, 2( 4): 32
9	G L, Nemhauser L A Wolsey . Best algorithms for approximating the maximum of a submodular set function. Mathematics of Operations Research, 1978, 3( 3): 177–188
10	U Feige . A threshold of ln n for approximating set cover. Journal of the ACM, 1998, 45( 4): 634–652
11	G L, Nemhauser L A, Wolsey M L Fisher . An analysis of approximations for maximizing submodular set functions—I. Mathematical Programming, 1978, 14(1): 265−294
12	S, Khuller A, Moss J Naor . The budgeted maximum coverage problem. Information Processing Letters, 1999, 70( 1): 39–45
13	M Sviridenko . A note on maximizing a submodular set function subject to a knapsack constraint. Operations Research Letters, 2004, 32( 1): 41–43
14	J Vondrak . 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	A, Kulik H, Shachnai T Tamir . 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	M, Feldman J, Naor R Schwartz . 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	N, Buchbinder M Feldman . 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	N, Buchbinder M Feldman . 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	N, Buchbinder M Feldman . Deterministic algorithms for submodular maximization problems. ACM Transactions on Algorithms, 2018, 14( 3): 32
20	X, Sun J, Zhang S, Zhang Z Zhang . Improved deterministic algorithms for non-monotone submodular maximization. In: Proceedings of Computing and Combinatorics: 28th International Conference. 2022, 496−507
21	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. 2014, 671−680
22	M, Feldman A, Norouzi-Fard O, Svensson R Zenklusen . 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	N, Alaluf A, Ene M, Feldman H L, Nguyen A Suh . An optimal streaming algorithm for submodular maximization with a cardinality constraint. Mathematics of Operations Research, 2022, 47( 4): 2667–2690
24	C C, Huang N, Kakimura Y Yoshida . Streaming algorithms for maximizing monotone submodular functions under a knapsack constraint. Algorithmica, 2020, 82( 4): 1006–1032
25	C C, Huang N Kakimura . Improved streaming algorithms for maximizing monotone submodular functions under a knapsack constraint. Algorithmica, 2021, 83( 3): 879–902
26	C C, Huang N Kakimura . Multi-pass streaming algorithms for monotone submodular function maximization. Theory of Computing Systems, 2022, 66( 1): 354–394
27	G, Yaroslavtsev S, Zhou D Avdiukhin . “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	R, Kumar B, Moseley S, Vassilvitskii A Vattani . Fast greedy algorithms in mapReduce and streaming. ACM Transactions on Parallel Computing, 2015, 2( 3): 14
29	Q, Yu E L, Xu S Cui . 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	A, Gupta A, Roth G, Schoenebeck K Talwar . 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	J, Lee V S, Mirrokni V, Nagarajan M Sviridenko . Maximizing nonmonotone submodular functions under matroid or knapsack constraints. SIAM Journal on Discrete Mathematics, 2010, 23( 4): 2053–2078
32	S, Fadaei M A, Fazli M A Safari . Maximizing non-monotone submodular set functions subject to different constraints: combined algorithms. Operations Research Letters, 2011, 39( 6): 447–451
33	N, Buchbinder M Feldman . Constrained submodular maximization via a nonsymmetric technique. Mathematics of Operations Research, 2019, 44( 3): 988–1005
34	X, Sun J, Zhang S, Zhang Z Zhang . Improved deterministic algorithms for non-monotone submodular maximization. Theoretical Computer Science, 2024, 984: 114293

[1]

Highlights

Download

Viewed

Full text

Abstract

Cited

Shared

Discussed