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
PDF (1.6 MB)
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.

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. 701711.
[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. 671680.
[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. 510520.
[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. 13581367.
[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. 137146.
[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. 12561266.
[7]
J. Wu and N. Wang, Approximating special social influence maximization problems, Tsinghua Science and Technology, vol. 25, no. 6, pp. 703711, 2020.
[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. 508516.
[9]
A. Krause, H. Brendan, C. Guestrin, and A. Gupta, Robust submodular observation selection, J. Mach. Learn. Res., vol. 9, no. 93, pp. 27612801, 2008.
[10]
J. B. Orlin, A. S. Schulz, and R. Udwani, Robust monotone submodular function maximization, Math. Program., vol. 172, no. 1, pp. 505537, 2018.
[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. 10141022.
[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. 22222232.
[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. 53565366.
[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. 839848.
[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. 587595.
[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. 467476.
[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. 265294, 1978.
[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. 26342643.
[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. 11971218, 2017.
[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. 784798.
[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. 6876, 2021.
[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. 13631374.
[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. 33113320.
[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. 38263835.
[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. 241254.
[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:114:18.
[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. 19141933.
[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. 14331452.
[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. 17401766, 2011.
[30]
U. Feige, A threshold of ln(n) for approximating set cover, J. ACM, vol. 45, no. 4, pp. 634652, 1998.
[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. 795806, 2010.
[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. 758784.
[33]
K. K. Sarpatwar, B. Schieber, and H. Shachnai, Constrained submodular maximization via greedy local search, Oper. Res. Lett., vol. 41, no. 1, pp. 16, 2019.
[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. 17561768.
[35]
C. Lu, W. Yang, and S. Gao, Regularized non-monotone submodular maximization, arXiv:2103.10008, 2021.
[36]
S. Chen, W. Yang, S. Gao, and R. Jin, Novel algorithms for maximum DS decomposition, Theor. Comput. Sci., vol. 857, pp. 8796, 2021.
[37]
M. Feldman, Guess free maximization of submodular and linear sums, Algorithmica, vol. 83, no. 3, pp. 853878, 2021.
[38]
S. Tang and J. Yuan, Adaptive regularized submodular maximization, in Proc. 32nd Int. Symp. on Algorithms and Computation, Fukuoka, Japan, 2021, pp. 69:179:13.
[39]
C. C. Huang, and N. Kakimura, Multipass streaming algorithms for monotone submodular function maximization, Theor. Comput. Syst., vol. 66, no. 1, pp. 354394, 2022.
[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. 13601368.
[41]
A. McGregor and H. T. Vu, Better streaming algorithms for the maximum coverage problem, Theor. Comput. Syst., vol. 63, no. 7, pp. 15951619, 2019.
[42]
A. Kuhnle, Quick streaming algorithms for cardinality-constrained maximization of non-monotone submodular functions in linear time, arXiv:2104.06873, 2021.
Tsinghua Science and Technology
Pages 76-85
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

429

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