次模函数最大化的流算法综述

doi:10.15960/j.cnki.issn.1007-6093.2020.02.006

摘要/Abstract

摘要： 次模函数优化在计算机科学、数学、经济学等学科得到广泛研究.大数据环境下的次模优化是相对较新的研究领域，受到更多关注.特别地，考虑基于流模型的次模最大化问题.在该问题中，数据以流的形式呈现，其目的是从数据流中抽取满足某些特性的稀疏子集，最大化次模收益函数值.介绍了基于流模型的次模最大化问题的阈值和优先权方法，同时也介绍了若干次模最大化变形的流算法进展.

关键词: 次模最大化, 大数据, 流算法

Abstract: While submodular function optimization has been studied extensively in computer science, mathematics, and economics, etc., submodular optimization in big data environment is a relatively new field that has attracted many attentions recently. In particular, submodular optimization with streaming data is the focus of this work. Facing real-time streaming data revealed in real time, the goal is to select a sparse subset satisfying certain desirable features from the stream to maximize certain submodular utility function. The main purpose of this paper is to provide suggestions for future research on this important class of problems. We introduce the threshold and preemption methods for the streaming submodular maximization problem. We also investigate the development of streaming algorithms for some variants of submodular maximization problems.

Key words: submodular maximization, big data, streaming algorithms

中图分类号:

O221.7

杨瑞琪, 徐大川, 杜东雷, 张冬梅. 次模函数最大化的流算法综述[J]. 运筹学学报, 2020, 24(2): 73-86.

YANG Ruiqi, XU Dachuan, DU Donglei, ZHANG Dongmei. A survey on streaming algorithms for maximizing submodular functions[J]. Operations Research Transactions, 2020, 24(2): 73-86.

参考文献

[1] Nemhauser G L, Wolsey L A, Fisher M L. An analysis of approximations for maximizing submodular set functions-I[J]. Mathematical Programming, 1978, 14:265-294.
[2] Kulik A, Shachnai H, Tamir T. Approximations for monotone and non-monotone submodular maximization with knapsack constraints[J]. Mathematics of Operations Research, 2013, 38:729-739.
[3] Sviridenko M. A note on maximizing a submodular set function subject to a knapsack constraint[J]. Operations Research Letters, 2004, 32:41-43.
[4] Calinescu G, Chekuri C, Pál M, et al. Maximizing a monotone submodular function subject to a matroid constraint[J]. SIAM Journal on Computing, 2011, 40:1740-1766.
[5] Fisher M L, Nemhauser G L, Wolsey L A. An analysis of approximations for maximizing submodular set functions)II[M].//Polyhedral Combinatorics. Heidelberg, Springer, 1978:73-87.
[6] Lee J, Sviridenko M, Vondrák J. Submodular maximization over multiple matroids via generalized exchange properties[J]. Mathematics of Operations Research, 2010, 35:795-806.
[7] Badanidiyuru A, Mirzasoleiman B, Karbasi A, et al. Streaming submodular maximization:Massive data summarization on the fly[C]//Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2014:671-680.
[8] Norouzi-Fard A, Tarnawski J, Mitrović S, et al. Beyond 1/2-approximation for submodular maximization on massive data streams[C]//Proceedings of the 35th International Conference on Machine Learning, 2018:3826-3835.
[9] Kazemi E, Mitrovic M, Zadimoghaddam M, et al. Submodular streaming in all its glory:Tight approximation, minimum memory and low adaptive complexity[C]//Proceedings of the 36th International Conference on Machine Learning, 2019:3311-3320.
[10] Agrawal S, Shadravan M, Stein C. Submodular secretary problem with shortlists[C]//Proceedings of the 10th Innovations in Theoretical Computer Science, 2019, 1:1-1:19.
[11] Feldman M, Norouzi-Fard A, Svensson O, et al. The one-way communication complexity of submodular maximization with applications to streaming and robustness[J]. ArXiv:2003.13459. To appear in STOC 2020.
[12] Alaluf N, Feldman M. Making a sieve random:Improved semi-streaming algorithm for submodular maximization under a cardinality constraint[J]. ArXiv:1906.11237, 2019.
[13] Alaluf N, Ene A, Feldman M, et al. Optimal streaming algorithms for submodular maximization with cardinality constraints[J]. ArXiv:1911.12959, 2019.
[14] Kazemi E, Minaee S, Feldman M, et al. Regularized submodular maximization at scale[J]. ArXiv:2002.03503, 2020.
[15] Huang C C, Kakimura N, Yoshida Y. Streaming algorithms for maximizing monotone submodular functions under a knapsack constraint[J]. Algorithmica, 2020, 82:1006-1032.
[16 Huang C C, Kakimura N. Improved streaming algorithms for maximizing monotone submodular functions under a knapsack constraint[C]//Proceedings of the 16th International Symposium Workshop on Algorithms and Data Structures, 2019:438-451.
[17] Li W, Shroff N. Efficient algorithms and lower bounds for submodular maximization[J]. ArXiv:1804.08178, 2018.
[18] Huang C C, Kakimura N. Multi-pass streaming algorithms for monotone submodular function maximization[J]. ArXiv:1802.06212, 2018.
[19] Avdiukhin D, Yaroslavtsev G, Zhou S. "Bring your own greedy"+max:Near-optimal 1/2-approximations for submodular knapsack[J]. ArXiv:1910.05646, 2019.
[20] Chekuri C, Gupta S, Quanrud K. Streaming algorithms for submodular function maximization[C]//Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming, 2015:318-330.
[21] Haba R, Kazemi E, Feldman M, et al. Streaming submodular maximization under a k-set system constraint[J]. ArXiv:2002.03352, 2020.
[22] Huang C C, Kakimura N, Mauras S, et al. Approximability of monotone submodular function maximization under cardinality and matroid constraints in the streaming model[J]. ArXiv:2002.05477, 2020.
[23] Kumar R, Moseley B, Vassilvitskii S, et al. Fast greedy algorithms in MapReduce and streaming[J]. ACM Transactions on Parallel Computing, 2015, 2(3):1-22.
[24] Feldman M, Karbasi A, Kazemi E. Do less, get more:Streaming submodular maximization with subsampling[C]//Proceedings of the 32nd Annual Conference on Neural Information Processing Systems, 2018:730-740.
[25] Shadravan M. Submodular matroid secretary problem with shortlists[J]. ArXiv:2001.00894, 2020.
[26] Mirzasoleiman B, Jegelka S, Krause A. Streaming non-monotone submodular maximization:Personalized video summarization on the fly[C]//Proceedings of the 32nd AAAI Conference on Artificial Intelligence, 2018:1379-1386.
[27] Chen J, Nguyen H L, Zhang Q. Submodular maximization over sliding windows[J]. ArXiv:1611.00129, 2016.
[28] Epasto A, Lattanzi S, Vassilvitskii S, et al. Submodular optimization over sliding windows[C]//Proceedings of the 26th International World Wide Web Conference, 2017:421-430.
[29] Zhao J, Shang S, Wang P, et al. Submodular optimization over streams with inhomogeneous decays[C]//Proceedings of the 33rd AAAI Conference on Artificial Intelligence, 2019:5861-5868.
[30] Buchbinder N, Feldman M, Schwartz R. Online submodular maximization with preemption[C]//Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms, 2015:1202-1216.
[31] Korula N, Mirrokni V, Zadimoghaddam, M. Online submodular welfare maximization:Greedy beats 1/2 in random order[J]. SIAM Journal on Computing, 2018, 47:1056-1086.
[32] Buchbinder N, Feldman M, Filmus Y, Garg M. Online submodular maximization:Beating 1/2 made simple[C]//Proceedings of the 21st International Conference on Integer Programming and Combinatorial Optimization, 2019:101-114.
[33] Chan T, Huang Z, Jiang S, et al. Online submodular maximization with free disposal:Randomization beats 1/4 for partition matroids[C]//Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms, 2017:1204-1223.
[34] Chan T, Jiang H, Tang Z, et al. Online submodular maximization problem with vector packing constraint[C]//Proceedings of the 25th European Symposium on Algorithms, 2017, 24:1-24:14.
[35] Kapralov M, Post I, Vondrak J. Online submodular welfare maximization:Greedy is optimal[C]//Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, 2013:1216-1225.
[36] Kesselheim T, Tönnis A. Submodular secretary problems:Cardinality, matching, and linear constraints[C]//Proceedings of the 20th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems and the 21st International Workshop on Randomization and Computation, 2017, 16:1-16:22.
[37] Wang Y, Li Y, Fan J, Tan K. Location-aware influence maximization over dynamic social streams[J]. ACM Transactions on Information Systems, 2018, 36(4):No. 43, 1-35.
[38] Yu Q, Li H, Liao Y, Cui S. Streaming influence maximization in social networks based on multi-action credit distribution[C]//Proceedings of the 2018 IEEE International Conference on Acoustics, Speech and Signal Processing, 2018:6378-6382.
[39] Bateni M, Esfandiari H, Mirrokni V. Almost optimal streaming algorithms for coverage problems[C]//Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures, 2017:13-24.
[40] McGregor A, Vu H T. Better streaming algorithms for the maximum coverage problem[J]. Theory of Computing Systems, 2019, 63:1595-1619.
[41] Barger A, Feldman D. K-means for streaming and distributed big sparse data[C]//Proceedings of the 16th SIAM International Conference on Data Mining, 2016:342-350.
[42] Lang H. Online facility location against a t-bounded adversary[C]//Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms, 2018:1002-1024.
[43] Schmidt M, Schwiegelshohn C, Sohler C. Fair coresets and streaming algorithms for fair kmeans clustering[C]//Proceedings of the 17th International Workshop on Approximation and Online Algorithms, 2020:232-251.
[44] Elenberg E R, Dimakis A G, Feldman M, et al. Streaming weak submodularity:Interpreting neural networks on the fly[C]//Proceedings of the 31st Annual Conference on Neural Information Processing Systems, 2017:4045-4055.
[45] Jiang Y, Wang Y, Xu D, et al. Streaming algorithm for maximizing a monotone non-submodular function under d-knapsack constraint[J]. Optimization Letters, DOI:10.1007/s11590-019-01430-z.
[46] Wang Y, Xu D, Wang Y, Zhang D. Non-submodular maximization on massive data streams[J]. Journal of Global Optimization, DOI:10.1007/s10898-019-00840-8.
[47] Yang R, Xu D, Li M, et al. Thresholding methods for streaming submodular maximization with a cardinality constraint and its variants[M].//Nonlinear Combinatorial Optimization, 2019:123-140. Springer Optimization and Its Applications, vol 147. Springer.
[48] Balkanski E, Mirzasoleiman B, Krause A, et al. Learning sparse combinatorial representations via two-stage submodular maximization[C]//Proceedings of the 33rd International Conference on Machine Learning, 2016:2207-2216.
[49] Stan S, Zadimoghaddam M, Krause A, et al. Probabilistic submodular maximization in sublinear time[C]//Proceedings of the 34th International Conference on Machine Learning, 2017:3241-3250.
[50] Yang R, Gu S, Gao C, et al. A two-stage constrained submodular maximization[C]//Proceedings of the 13th International Conference on Algorithmic Applications in Management, 2019:329-340.
[51] Mitrovic M, Kazemi E, Zadimoghaddam M, et al. Data summarization at scale:A twostage submodular approach[C]//Proceedings of the 35th International Conference on Machine Learning, 2018:3593-3602.
[52] Kempe D, Kleinberg J, Tardos É. Maximizing the spread of influence through a social network[C]//Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2003:137-146.
[53] Horel T, Singer Y. Maximization of approximately submodular functions[C]//Proceedings of the 30th International Conference on Neural Information Processing Systems, 2016:3053-3061.
[54] Hassidim A, Singer Y. Submodular optimization under noise[C]//Proceedings of the 30th Conference on Learning Theory, 2017:1069-1122.
[55] Qian C, Shi J, Yu Y, et al. Subset selection under noise[C]//Proceedings of the 31st Annual Conference on Neural Information Processing Systems, 2017:3560-3570.
[56] Gölz P, Procaccia A D. Migration as submodular optimization[C]//Proceedings of the 33rd AAAI Conference on Artificial Intelligence, 2019:549-556.
[57] Singer Y, Hassidim A. Optimization for approximate submodularity[C]//Proceedings of the 32nd Annual Conference on Neural Information Processing Systems, 2018:396-407.
[58] Yang R, Xu D, Cheng Y, et al. Streaming submodular maximization under noises[C]//Proceedings of the 39th IEEE International Conference on Distributed Computing Systems, 2019:348-357.
[59] Krause A, McMahan H B, Guestrin C, et al. Robust submodular observation selection[J]. Journal of Machine Learning Research, 2008, 9:2761-2801.
[60] Orlin J, Schulz A, Udwani R. Robust monotone submodular function maximization[J]. Mathematical Programming, 2018, 172:505-537.
[61] Bogunovic I, Mitrović S, Scarlett J, et al. Robust submodular maximization:A non-uniform partitioning approach[C]//Proceedings of the 34th International Conference on Machine Learning, 2017:508-516.
[62] Mitrović S, Bogunovic I, Norouzi-Fard A, et al. Streaming robust submodular maximization:A partitioned thresholding approach[C]//Proceedings of the 31st Annual Conference on Neural Information Processing Systems, 2017:4560-4569.
[63] Avdiukhin D, Mitrovic S, Yaroslavtsev G, et al. Adversarially robust submodular maximization under knapsack constraints[C]. Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2019:148-156.
[64] Tschiatschek S, Singla A, Krause A. Selecting sequences of items via submodular maximization[C]//Proceedings of the 31st AAAI Conference on Artificial Intelligence, 2017:2667-2673.
[65] Mitrovic M, Feldman M, Krause A, et al. Submodularity on hypergraphs:From sets to sequences[C]//Proceedings of the 21st International Conference on Artificial Intelligence and Statistics, 2018:1177-1184.
[66] Mitrovic M, Kazemi E, Feldman M, et al. Adaptive sequence submodularity[C]//Proceedings of the 33rd Annual Conference on Neural Information Processing Systems, 2019:5353-5364.
[67] Yang R, Xu D, Guo L, et al. Sequence submodular maximization meets streaming[C]//Proceedings of the 13th Annual International Conference on Combinatorial Optimization and Applications, 2019:565-575.