AI Chat Paper
Note: Please note that the following content is generated by AMiner AI. SciOpen does not take any responsibility related to this content.
{{lang === 'zh_CN' ? '文章概述' : 'Summary'}}
{{lang === 'en_US' ? '中' : 'Eng'}}
Chat more with AI
Powered by AMiner. Clicking this button will take you away from SciOpen.
Home Tsinghua Science and Technology Article
PDF (1.6 MB)
Cite
EndNote(RIS) BibTeX
Collect
Submit Manuscript AI Chat Paper
Show Outline
Outline
Show full outline
Hide outline
Outline
Show full outline
Hide outline
Open Access

Multipass Streaming Algorithms for Regularized Submodular Maximization

Beijing Institute for Scientific and Engineering Computing, Beijing University of Technology, Beijing 100124. China
School of Mathematical Sciences, University of Chinese Academy Sciences, Beijing 100049, China
Beijing Jinghang Research Institute of Computing and Communication, Beijing 100074, China
Show Author Information

Abstract

In this work, we study a k-Cardinality Constrained Regularized Submodular Maximization ( k-CCRSM) problem, in which the objective utility is expressed as the difference between a non-negative submodular and a modular function. No multiplicative approximation algorithm exists for the regularized model, and most works have focused on designing weak approximation algorithms for this problem. In this study, we consider the k-CCRSM problem in a streaming fashion, wherein the elements are assumed to be visited individually and cannot be entirely stored in memory. We propose two multipass streaming algorithms with theoretical guarantees for the above problem, wherein submodular terms are monotonic and nonmonotonic.

Keywords

submodular optimizationregularized modelstreaming algorithmsthreshold

References

[1]
Q. Gong, S. Gao, F. Wang, and R. Yang, A multipass streaming algorithm for regularized submodular maximization, in Proc. 15th Ann. Int. Conf. on Combinatorial Optimization and Applications, Tianjin, China, 2021, pp. 701–711.
Crossref Google Scholar
[2]
A. Badanidiyuru, B. Mirzasoleiman, A. Karbasi, and A. Krause, Streaming submodular maximization: Massive data summarization on the fly, in Proc. 20th ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining, New York, NY, USA, 2014, pp. 671–680.
Crossref Google Scholar
[3]
H. Lin and J. Bilmes, A class of submodular functions for document summarization, in Proc. 49th Ann. Meeting of the Association for Computational Linguistics: Human Language Technologies, Portland, OR, USA, 2011, pp. 510–520.
Google Scholar
[4]
B. Mirzasoleiman, A. Badanidiyuru, and A. Karbasi, Fast constrained submodular maximization: Personalized data summarization, in Proc. 33nd Int. Conf. on Machine Learning, New York, NY, USA, 2016, pp. 1358–1367.
Google Scholar
[5]
D. Kempe, J. Kleinberg, and É. Tardos, Maximizing the spread of influence through a social network, in Proc. 9th ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining, Washington, DC, USA, 2003, pp. 137–146.
Crossref Google Scholar
[6]
S. M. Nikolakaki, A. Ene, and E. Terzi, An efficient framwork for balancing submodularity and cost, in Proc. 27th ACM SIGKDD Conf. on Knowledge Discovery and Data Mining, Virtual Event, 2021, pp. 1256–1266.
Crossref Google Scholar
[7]
J. Wu and N. Wang, Approximating special social influence maximization problems, Tsinghua Science and Technology, vol. 25, no. 6, pp. 703–711, 2020.
Crossref Google Scholar
[8]
I. Bogunovic, S. Mitrović, J. Scarlett, and V. Cevher, Robust submodular maximization: A non-uniform partitioning approach, in Proc. 34th Int. Conf. on Machine Learning, Sydney, Australia, 2017, pp. 508–516.
Google Scholar
[9]
A. Krause, H. Brendan, C. Guestrin, and A. Gupta, Robust submodular observation selection, J. Mach. Learn. Res., vol. 9, no. 93, pp. 2761–2801, 2008.
Google Scholar
[10]
J. B. Orlin, A. S. Schulz, and R. Udwani, Robust monotone submodular function maximization, Math. Program., vol. 172, no. 1, pp. 505–537, 2018.
Crossref Google Scholar
[11]
A. Dasgupta, R. Kumar, and S. Ravi, Summarization through submodularity and dispersion, in Proc. 51st Ann. Meeting of the Association for Computational Linguistics, Sofia, Bulgaria, 2013, pp. 1014–1022.
Google Scholar
[12]
S. Cui, K. Han, T. Zhu, J. Tang, B. Wu, and H. Huang, Randomized algorithms for submodular function maximization with a k-system constraint, in Proc. 38th Int. Conf. on Machine Learning, Virtual Event, 2021, pp. 2222–2232.
Google Scholar
[13]
E. Kazemi, S. Minaee, M. Feldman, and A. Karbasi, Regularized submodular maximization at scale, in Proc. 38th Int. Conf. on Machine Learning, Virtual Event, 2021, pp. 5356–5366.
Google Scholar
[14]
A. Anagnostopoulos, L. Becchetti, C. Castillo, A. Gionis, and S. Leonardi, Online team formation in social networks, in Proc. 21st Int. World Wide Web Conferences, Lyon, France, 2012, pp. 839–848.
Crossref Google Scholar
[15]
M. Kargar, M. Zihayat, and A. An, Finding affordable and collaborative teams from a network of experts, in Proc. 13th SIAM Int. Conf. on Data Mining, Austin, TX, USA, 2013, pp. 587–595.
Crossref Google Scholar
[16]
T. Lappas, K. Liu, and E. Terzi, Finding a team of experts in social networks, in Proc. 15th ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining, Paris, France, 2009, pp. 467–476.
Crossref Google Scholar
[17]
G. L. Nemhauser, L. A. Wolsey, and M. L. Fisher. An analysis of approximations for maximizing submodular set functions-I, Math. Program., vol. 14, no. 1, pp. 265–294, 1978.
Crossref Google Scholar
[18]
C. Harshaw, M. Feldman, J. Ward, and A. Karbasi, Submodular maximization beyond non-negativity: Guarantees, fast algorithms, and applications, in Proc. 36th Int. Conf. on Machine Learning, Long Beach, CA, USA, 2019, pp. 2634–2643.
Google Scholar
[19]
M. Sviridenko, J. Vondrák, and J. Ward, Optimal approximation for submodular and supermodular optimization with bounded curvature, Math. Oper. Res., vol. 42, no. 4, pp. 1197–1218, 2017.
Crossref Google Scholar
[20]
M. Feldman, J. Naor, R. Schwartz, and J. Ward, Improved approximations for k-exchange systems, in Proc. 19th Ann. European Symposium on Algorithms, Saarbrücken, Germany, 2011, pp. 784–798.
Crossref Google Scholar
[21]
Y. Wang, D. Xu, D. Du, and R. Ma, Bicriteria algorithms to balance coverage and cost in team formation under online model, Theor. Comput. Sci., vol. 854, pp. 68–76, 2021.
Crossref Google Scholar
[22]
M. Feldman, A. Norouzi-Fard, O. Svensson, and R. Zenklusen, The one-way communication complexity of submodular maximization with applications to streaming and robustness, in Proc. 52nd Ann. ACM SIGACT Symp. on Theory on Computing, Chicago, IL, USA, 2020, pp. 1363–1374.
Crossref Google Scholar
[23]
E. Kazemi, M. Mitrovic, M. Zadimoghaddam, S. Lattanzi, and A. Karbasi, Submodular streaming in all its glory: Tight approximation, minimum memory and low adaptive complexity, in Proc. 38th Int. Conf. on Machine Learning, Long Beach, CA, USA, 2019, pp. 3311–3320.
Google Scholar
[24]
A. Norouzi-Fard, J. Tarnawski, S. Mitrovic, A. Zandieh, A. Mousavifar, and O. Svensson, Beyond 1/2-approximation for submodular maximization on massive data streams, in Proc. 35th Int. Conf. on Machine Learning, Stockholmsmässan, Sweden, 2018, pp. 3826–3835.
Google Scholar
[25]
N. Buchbinder, M. Feldman, and M. Garg, Deterministic (1/2+ε)-approximation for submodular maximization over a matroid, in Proc. 30th Ann. ACM-SIAM Symp. on Discrete Algorithms, San Diego, CA, USA, 2019, pp. 241–254.
Crossref Google Scholar
[26]
C. C. Huang and F. Sellier, Semi-streaming algorithms for submodular function maximization under b-matching, matroid, and matchoid constraints, in Proc. 25th Int. Workshop on Randomization and Computation (RANDOM 2021) and 24th Int. Workshop on Approximation Algorithms for Combinatorial Optimization Problems, Seattle, WA, USA, 2021, pp. 14:1–14:18.
Google Scholar
[27]
R. Levin and D. Wajc, Streaming submodular matching meets the primal-dual method, in Proc. 32nd ACM-SIAM Symp. on Discrete Algorithms, Alexandria, VA, USA, 2021, pp. 1914–1933.
Crossref Google Scholar
[28]
N. Buchbinder, M. Feldman, J. Naor, and R. Schwartz, Submodular maximization with cardinality constraints, in Proc. 25th Ann. ACM-SIAM Symp. on Discrete Algorithms, Portland, OR, USA, 2014, pp. 1433–1452.
Crossref Google Scholar
[29]
G. Calinescu, C. Chekuri, M. Pál, and J. Vondrák, Maximizing a monotone submodular function subject to a matroid constraint, SIAM J. Comput., vol. 40, no. 6, pp. 1740–1766, 2011.
Crossref Google Scholar
[30]
U. Feige, A threshold of ln⁡(n) for approximating set cover, J. ACM, vol. 45, no. 4, pp. 634–652, 1998.
Crossref Google Scholar
[31]
J. Lee, M. Sviridenko, and J. Vondrák, Submodular maximization over multiple matroids via generalized exchange properties, Math. Oper. Res., vol. 35, no. 4, pp. 795–806, 2010.
Crossref Google Scholar
[32]
M. Feldman, C. Harshaw, and A. Karbasi, Greed is good: Near-optimal submodular maximization via greedy optimization, in Proc. 30th Conf. on Learning Theory, Amsterdam, The Netherlands, 2017, pp. 758–784.
Google Scholar
[33]
K. K. Sarpatwar, B. Schieber, and H. Shachnai, Constrained submodular maximization via greedy local search, Oper. Res. Lett., vol. 41, no. 1, pp. 1–6, 2019.
Crossref Google Scholar
[34]
T. Jin, Y. Yang, R. Yang, J. Shi, K. Huang, and X. Xiao, Unconstrained submodular maximization with modular costs: Tight approximation and applicatiion to profit maximization. in Proc. 47th Int. Conf. on Very Large Databases, Copenhagen, Denmark, 2021, pp. 1756–1768.
Crossref Google Scholar
[35]
C. Lu, W. Yang, and S. Gao, Regularized non-monotone submodular maximization, arXiv:2103.10008, 2021.
Google Scholar
[36]
S. Chen, W. Yang, S. Gao, and R. Jin, Novel algorithms for maximum DS decomposition, Theor. Comput. Sci., vol. 857, pp. 87–96, 2021.
Crossref Google Scholar
[37]
M. Feldman, Guess free maximization of submodular and linear sums, Algorithmica, vol. 83, no. 3, pp. 853–878, 2021.
Crossref Google Scholar
[38]
S. Tang and J. Yuan, Adaptive regularized submodular maximization, in Proc. 32nd Int. Symp. on Algorithms and Computation, Fukuoka, Japan, 2021, pp. 69:1–79:13.
Google Scholar
[39]
C. C. Huang, and N. Kakimura, Multipass streaming algorithms for monotone submodular function maximization, Theor. Comput. Syst., vol. 66, no. 1, pp. 354–394, 2022.
Crossref Google Scholar
[40]
A. Kuhnle, Quick streaming algorithms for the maximizing of monotone submodular functions in linear time, in Proc. 24th Int. Conf. on Artificial Intelligence and Statistics, Virtual Event, 2021, pp. 1360–1368.
Google Scholar
[41]
A. McGregor and H. T. Vu, Better streaming algorithms for the maximum coverage problem, Theor. Comput. Syst., vol. 63, no. 7, pp. 1595–1619, 2019.
Crossref Google Scholar
[42]
A. Kuhnle, Quick streaming algorithms for cardinality-constrained maximization of non-monotone submodular functions in linear time, arXiv:2104.06873, 2021.
Google Scholar
Tsinghua Science and Technology
Volume 29 Issue 1,
February 2024
Pages 76-85
DOI: 10.26599/TST.2023.9010026
Cite this article:
Gong Q, Gao S, Wang F, et al. Multipass Streaming Algorithms for Regularized Submodular Maximization. Tsinghua Science and Technology, 2024, 29(1): 76-85. https://doi.org/10.26599/TST.2023.9010026

426

Views

40

Downloads

0

Crossref

0

Web of Science

0

Scopus

0

CSCD

Altmetrics
Received: 10 March 2022
Revised: 06 January 2023
Accepted: 11 March 2023
Published: 21 August 2023
© The author(s) 2024.

The articles published in this open access journal are distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/).
Return