带基数约束的次模+超模(BP)函数最大化问题的流算法

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

Abstract

Abstract:

In this paper, wepropose streaming algorithms for the maximization ofsubmodular+supermodular functions with cardinality constraint, whichhas wide applications in data processing, machine learning andartificial intelligence. By means of the diminishing return ratioof the objective function, we design a one-pass sieve-streamingalgorithm and get the approximate ratio $\min\left\{\frac{(1-\varepsilon)\gamma}{2^{\gamma}}, 1-\frac{\gamma}{2^{\gamma}(1-\kappa^{g})^{2}}\right\}$. Numerical experiments show that the sieve-streaming algorithm is effective forthe BP-maximization problem and can guarantee the same result asthe greedy algorithm with less time if submodular function andsupermodular are in the same order of magnitude.

Key words: BP-function maximization, total curvature, diminishing return ratio, streaming algorithm, cardinality constraint

CLC Number:

O221.7

Yuefang LIAN, Zhenning ZHANG, Zhongrui ZHAO, Dingzhu DU. Streaming algorithms for the maximization of submodular+supermodular functions with a cardinality constraint[J]. Operations Research Transactions, 2022, 26(1): 85-98.

Figures/Tables 3

References 31

1	Agrawal R, Gollapudi S, Halverson A, et al. Diversifying search results[C]//Proceedings of the Second ACM International Conference on Web Search and Data Mining, 2009: 5-14.
2	Golovin D , Krause A . Adaptive submodularity: Theory and applications in active learning and stochastic optimization[J]. Journal of Artificial Intelligence Research, 2012, 42 (1): 427- 486.
3	Gomez-Rodriguez M , Leskovec J , Krause A . Inferring networks of diffusion and influence[J]. ACM Transactions on Knowledge Discovery from Data, 2010, 5 (4): 1- 37.
4	Kempe D, Kleinberg J, Tardos E. Maximizing the spread of influence through a social network[C]//Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2003: 137-146.
5	Wei K, Iyer R, Bilmes J. Submodularity in data subset selection and active learning[C]//Proceedings of International Conference on Machine Learning (ICML), 2015.
6	Topkis D M . Supermodularity and Complementarity[M]. Princeton: Princeton University Press, 2011.
7	Nemhauser G L , Wolsey L A , Fisher M L . An analysis of approximations for maximizing submodular set functions-I[J]. Mathematical Programming, 1978, 14 (1): 265- 294. doi: 10.1007/BF01588971
8	Conforti M , Cornuéjols G . Submodular set functions, matroids and the greedy algorithm: tight worst-case bounds and some generalizations of the Rado-Edmonds theorem[J]. Discrete Applied Mathematics, 1984, 7 (3): 251- 274. doi: 10.1016/0166-218X(84)90003-9
9	Sviridenko M , Vondrák , J , Ward J . Optimal approximation for submodular and supermodular optimization with bounded curvature[J]. Mathematics of Operations Research, 2017, 42 (4): 1197- 1218. doi: 10.1287/moor.2016.0842
10	Bai W, Bilmes J A. Greed is Still Good: Maximizing Monotone Submodular+Supermodular (BP)functions[C]//International Conference on Machine Learning, 2018: 304-313.
11	Ji S, Xu D, Li M, et al. Stochastic greedy algorithm is still good: Maximizing submodular+ supermodular functions[C]//World Congress on Global Optimization, 2019: 488-497.
12	Muthukrishnan S. Data streams: algorithms and applications[M]//Foundations and Trends in Theoretical Computer Science, 2005: 117-236.
13	Ajtai M, Jayram T S, Kumar R, et al. Approximate counting of inversions in a data stream[C]//Proceedings of the thiry-fourth annual ACM symposium on Theory of Computing, 2002: 370-379.
14	Dueck D, Frey B J. Non-metric affinity propagation for unsupervised image categorization[C]//2007 IEEE 11th International Conference on Computer Vision, 2007: 1-8.
15	El-Arini K, Guestrin C. Beyond keyword search: discovering relevant scientific literature[C]//Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2011: 439-447.
16	El-Arini K, Veda G, Shahaf D, et al. Turning down the noise in the blogosphere[C]//Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2009: 289-298.
17	Gomes R, Krause A. Budgeted nonparametric learning from data streams[C]//Proceedings of the 27th International Conference on International Conference on Machine Learning, 2010: 391-398.
18	Zoubin G. Scaling the indian buffet process via submodular maximization[C]//International Conference on Machine Learning, 2013: 1013-1021.
19	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.
20	Yu Q , Li H , Liao Y , et al. Fast budgeted influence maximization over multi-action event logs[J]. IEEE Access, 2018, 6, 14367- 14378. doi: 10.1109/ACCESS.2018.2809547
21	Norouzi-Fard A, Tarnawski J, Mitrovic S, et al. Beyond 1/2-approximation for submodular maximization on massive data streams[C]//International Conference on Machine Learning, 2018: 3826-3835.
22	Elenberg E, Dimakis A G, Feldman M, et al. Streaming weak submodularity: interpreting neural networks on the fly[C]//Proceedings of the 31st International Conference on Neural Information Processing Systems, 2017: 4044-4054.
23	Wang Y J , Xu D C , Wang Y S , et al. Non-submodular maximization on massive data streams[J]. Journal of Global Optimization, 2020, 76 (4): 729- 743. doi: 10.1007/s10898-019-00840-8
24	Barbosa R, Ene A, Nguyen H L, et al. The power of randomization: distributed submodular maximization on massive datasets[C]//International Conference on Machine Learning, 2015: 236-1244.
25	Barbosa R, Ene A, Nguyen H L, et al. A new framework for distributed submodular maximiza tion[C]//2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), 2016: 645-654.
26	Buchbinder N, Feldman M, Schwartz R. Online submodular maximization with preemption[C]//Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms, 2014: 1202-1216.
27	Chakrabarti A , Kale S . Submodular maximization meets streaming: matchings, matroids, and more[J]. Mathematical Programming, 2015, 154 (1): 225- 247.
28	Mirzasoleiman B, Badanidiyuru A, Karbasi A, et al. Lazier than lazy greedy[C]//Proceedings of the AAAI Conference on Artificial Intelligence, 2015: 1812-1818.
29	Fujishige S . Submodular Functions and Optimization[M]. Amsterdam: Elsevier, 2005.
30	Bian A A, Buhmann J M, Krause A, et al. Guarantees for greedy maximization of non submodular functions with applications[C]//Proceedings of the 34th International Conference on Machine Learning (ICML), 2017: 498-507.
31	杨瑞琪, 徐大川, 杜东雷, 等. 次模函数最大化的流算法综述[J]. 运筹学学报, 2020, 24 (2): 73- 86.

性能	近似比	存储空间	运行时间	读取次数
算法1	$ \min\left\{\frac{\alpha\gamma}{2^{\gamma}}, 1-\frac{\gamma}{2^{\gamma}(1-\kappa^{g})}\right\} $	$ k $	$ \mathrm{O}(1) $	1
算法2	$ \min\left\{\frac{(1-\varepsilon)\gamma}{2^{\gamma}}, 1-\frac{\gamma}{2^{\gamma}(1-\kappa^{g})}\right\} $	$ O\left(\frac{k \log (k/\gamma)}{\varepsilon}\right) $	$ O\left(\frac{\log (k/\gamma)}{\varepsilon}\right) $	2
算法3	$ \min\left\{\frac{(1-\varepsilon)\gamma}{2^{\gamma}}, 1-\frac{\gamma}{2^{\gamma}(1-\kappa^{g})^{2}}\right\} $	$ O\left(\frac{k\log (k / \gamma)}{\varepsilon}\right) $	$ O\left(\frac{\log (k / \gamma)}{\varepsilon}\right) $	1

[1]	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.
[2]	SUN Xiaoling, LI Duan. Recent advances in integer programming [J]. Operations Research Transactions, 2014, 18(1): 39-68.

Streaming algorithms for the maximization of submodular+supermodular functions with a cardinality constraint

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 3

References 31

Related Articles 2

Recommended Articles

Metrics

Comments