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

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

CLC Number:

O221.7

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.

References

[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.

A survey on streaming algorithms for maximizing submodular functions

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

Comments

[1]	CHEN Feng. Research and application of operations research on intelligent scheduling decision support system for automotive outbound logistics [J]. Operations Research Transactions, 2021, 25(3): 37-73.
[2]	HUANG Jidan, ZHENG Feifeng, XU Yingfeng, LIU Ming. Parallel machine scheduling with deteriorating installation times in the MapReduce system [J]. Operations Research Transactions, 2020, 24(4): 93-106.
[3]	LIN Hao, LIN Lan. Optimality characterization of the minimum stretch spanning tree problem for interval graphs [J]. Operations Research Transactions, 2020, 24(4): 153-158.
[4]	ZHANG Yuzhong. A survey on job scheduling with rejection [J]. Operations Research Transactions, 2020, 24(2): 111-130.
[5]	CHEN Rubing, YUAN Jinjiang. Single-machine scheduling to minimize total weighted late work with positional due-indices [J]. Operations Research Transactions, 2020, 24(2): 131-144.
[6]	LIU Mingxi, GAN Guohua, CHENG Yukun, XIAO Lin, LIU Shuai, FANG Yong. Development and prospect of blockchain consensus mechanism [J]. Operations Research Transactions, 2020, 24(1): 23-39.
[7]	LIU Xiaoxia, YU Shanshan, LUO Wenchang. Approximation algorithms for single machine parallelbatch scheduling with release dates subject to the number of rejected jobs not exceeding a given threshold [J]. Operations Research Transactions, 2020, 24(1): 131-139.
[8]	LIN Hao, LIN Lan. The minimum cover flow problem in networks [J]. Operations Research Transactions, 2014, 18(4): 96-104.
[9]	WAN Long. An optimal algorithm for the two-order multiple problem [J]. Operations Research Transactions, 2014, 18(3): 99-103.
[10]	XU Dachuan, WAN Wei, WU Chenchen, XU Wenqing. A primal-dual approximation algorithm for stochastic fault-tolerant facility location problem [J]. Operations Research Transactions, 2014, 18(2): 17-28.
[11]	CHEN Xujin, XU Dachuan, ZHANG Guochuan. New perspectives of several fundamental problems in combinatorial optimization [J]. Operations Research Transactions, 2014, 18(1): 149-158.
[12]	ZHANG Huizhen, WEI Xin, MA Liang. A new solution method by linearization for a special kind of quadratic assignment problem [J]. Operations Research Transactions, 2013, 17(4): 87-95.
[13]	WANG Xing, XU Dachuan. Facility location problem with submodular penalties and stochastic demands [J]. Operations Research Transactions, 2013, 17(2): 1-9.
[14]	SHUAI Tianping,YU Jinguo,SUN Ling. A simulated annealing algorithm for the hybrid flow shop scheduling to minimize the number of tardy jobs [J]. Operations Research Transactions, 2013, 17(2): 41-47.
[15]	ZHANG Guochuan, CHEN Lin. The load balancing problem [J]. Operations Research Transactions, 2019, 23(3): 1-14.