Journal Home > Volume 29 , Issue 1
Tsinghua Science and Technology 2024, 29(1): 76-85 https://doi.org/10.26599/TST.2023.9010026
Open Access | Issue | Published: 21 August 2023

Multipass Streaming Algorithms for Regularized Submodular Maximization

Show Author's Information Qinqin Gong1,  Suixiang Gao2,  Fengmin Wang3,  Ruiqi Yang1( )
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
Keywords:
threshold, submodular optimization, streaming algorithms, regularized model
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
Download citation
EndNote(RIS)
BibTeX

185

Views

33

Downloads

Citations

0

Crossref

0

WoS

0

Scopus

0

CSCD

Abstract Full text About this article

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.


menu
Abstract
Full text
Outline
About this article

Multipass Streaming Algorithms for Regularized Submodular Maximization

Show Author's information Qinqin Gong1, Suixiang Gao2, Fengmin Wang3, Ruiqi Yang1( )
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

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: threshold, submodular optimization, streaming algorithms, regularized model

References(42)

[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.
DOI 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.
DOI 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.
DOI 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.
DOI 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.
DOI 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.
DOI 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.
DOI 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.
DOI 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.
DOI 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.
DOI 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.
DOI 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.
DOI 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.
DOI 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.
DOI 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.
DOI 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.
DOI 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.
DOI 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.
DOI Google Scholar
[30]
U. Feige, A threshold of ln⁡(n) for approximating set cover, J. ACM, vol. 45, no. 4, pp. 634–652, 1998.
DOI 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.
DOI 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.
DOI 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.
DOI 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.
DOI Google Scholar
[37]
M. Feldman, Guess free maximization of submodular and linear sums, Algorithmica, vol. 83, no. 3, pp. 853–878, 2021.
DOI 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.
DOI 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.
DOI 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
Publication history
Copyright
Acknowledgements
Rights and permissions

Publication history

Received: 10 March 2022
Revised: 06 January 2023
Accepted: 11 March 2023
Published: 21 August 2023
Issue date: February 2024

Copyright

© The author(s) 2024.

Acknowledgements

This work was supported by the Beijing Natural Science Foundation Project (No. Z220004), the National Natural Science Foundation of China (Nos. 11901544 and 12101587), and the China Postdoctoral Science Foundation (No. 2022M720329).

Rights and permissions

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