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 (413 KB)
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

A Note on Maximizing Regularized Submodular Functions Under Streaming

Beijing Institute for Scientific and Engineering Computing, Beijing University of Technology, Beijing 100124, China
Show Author Information

Abstract

Recent progress in maximizing submodular functions with a cardinality constraint through centralized and streaming modes has demonstrated a wide range of applications and also developed comprehensive theoretical guarantees. The submodularity was investigated to capture the diversity and representativeness of the utilities, and the monotonicity has the advantage of improving the coverage. Regularized submodular optimization models were developed in the latest studies (such as a house on fire), which aimed to sieve subsets with constraints to optimize regularized utilities. This study is motivated by the setting in which the input stream is partitioned into several disjoint parts, and each part has a limited size constraint. A first threshold-based bicriteria (1/3,2/3)-approximation for the problem is provided.

Keywords

submodular optimizationregular modelstreaming algorithmsthreshold technique

References

[1]
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
[2]
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
[3]
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
[4]
Y. Filmus and J. Ward, A tight combinatorial algorithm for submodular maximization subject to a matroid constraint, in Proc. 53rd IEEE Ann. Symp. on Foundations of Computer Science, New Brunswick, NJ, USA, 2012, pp. 659–668.
Crossref Google Scholar
[5]
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
[6]
A. Badanidiyuru, A. Karbasi, E. Kazemi, and J. Vondrák, Submodular maximization through barrier functions, in Proc. 34th Int. Conf. on Neural Information Processing Systems, Vancouver, Canada, 2020, pp. 524–534.
Google Scholar
[7]
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
[8]
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
[9]
A. Gupta, A. Roth, G. Schoenebeck, and K. Talwar, Constrained non-monotone submodular maximization: Offline and secretary algorithms, in Proc. 6th Int. Workshop on Internet and Network Economics, Stanford, CA, USA, 2010, pp. 246–257.
Crossref Google Scholar
[10]
M. Feldman, Guess free maximization of submodular and linear sums, Algorithmica, vol. 83, no. 3, pp. 853–878, 2021.
Crossref Google Scholar
[11]
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
[12]
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
[13]
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
[14]
Z. Abbassi, V. S. Mirrokni, and M. Thakur, Diversity maximization under matroid constraints, in Proc. 19th ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining, Chicago, IL, USA, 2013, pp. 32–40.
Crossref Google Scholar
[15]
M. Sviridenko, A note on maximizing a submodular set function subject to a knapsack constraint, Oper. Res. Lett., vol. 32, no. 1, pp. 41–43, 2004.
Crossref Google Scholar
[16]
U. Feige, A threshold of ln⁡n for approximating set cover, J. ACM, vol. 45, no. 4, pp. 634–652, 1998.
Crossref Google Scholar
[17]
C. Lu, W. Yang, and S. Gao, Regularized non-monotone submodular maximization, Optimization, , 2022.
Crossref Google Scholar
[18]
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, Proc. VLDB Endow., vol. 14, no. 10, pp. 1756–1768, 2021.
Crossref Google Scholar
[19]
S. M. Nikolakaki, A. Ene, and E. Terzi, An efficient framework for balancing submodularity and cost, arXiv preprint arXiv:2002.07782, 2020.
Crossref Google Scholar
[20]
S. Tang and J. Yuan, Adaptive regularized submodular maximization, in Proc. 32nd Int. Symp. on Algorithms and Computation, Fukuoka, Japan, 2021, vol. 212, pp. 69:1–69:13.
Google Scholar
[21]
N. Alaluf, A. Ene, M. Feldman, H. L. Nguyen, and A. Suh, An optimal streaming algorithm for submodular maximization with a cardinality constraint, Math. Oper. Res., vol. 47, no. 4, pp. 2667–2690, 2022.
Crossref Google Scholar
[22]
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
[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. 36th Int. Conf. on Machine Learning, Long Beach, CA, USA, 2019, pp. 3311–3320.
Google Scholar
[24]
S. Mitrovic, I. Bogunovic, A. Norouzi-Fard, J. M. Tarnawski, and V. Cevher, Streaming robust submodular maximization: A partitioned thresholding approach, in Proc. 31st Int. Conf. on Neural Information Processing Systems, Long Beach, CA, USA, 2017, pp. 4557–4566.
Google Scholar
[25]
C. C. Huang and N. Kakimura, Improved streaming algorithms for maximizing monotone submodular functions under a knapsack constraint, Algorithmica, vol. 83, no. 3, pp. 879–902, 2021.
Crossref Google Scholar
[26]
C. C. Huang, N. Kakimura, and Y. Yoshida, Streaming algorithms for maximizing monotone submodular functions under a knapsack constraint, Algorithmica, vol. 82, no. 4, pp. 1006–1032, 2020.
Crossref Google Scholar
[27]
C. Chekuri, S. Gupta, and K. Quanrud, Streaming algorithms for submodular function maximization, in Proc. 42nd Int. Colloquium on Automata, Languages, and Programming, Kyoto, Japan, 2015, pp. 318–330.
Crossref Google Scholar
[28]
M. Feldman, A. Karbasi, and E. Kazemi, Do less, get more: Streaming submodular maximization with subsampling, in Proc. 32nd Ann. Conf. on Neural Information Processing Systems, Montréal, Canada, 2018, pp. 730–740.
Google Scholar
[29]
R. Haba, E. Kazemi, M. Feldman, and A. Karbasi, Streaming submodular maximization under a k-set system constraint, in Proc. 37th Int. Conf. on Machine Learning, Virvual Event, 2020, pp. 3939–3949.
Google Scholar
[30]
A. Chakrabarti and S. Kale, Submodular maximization meets streaming: matchings, matroids, and more. Math. Program., vol. 154, nos. 1&2, pp. 225–247, 2015.
Crossref Google Scholar
[31]
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
[32]
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, 2021, Virtual Event, pp. 14:1–14:18.
Google Scholar
[33]
P. Garg, L. Jordan, and O. Svensson, Semi-streaming algorithms for submodular matroid intersection, in Proc. 22nd Int. Conf. on Integer Programming and Combinatorial Optimization, Atlanta, GA, USA, 2021, pp. 208–222.
Crossref Google Scholar
[34]
S. Agrawal, M. Shadravan, and C. Stein, Submodular secretary problem with shortlists, in Proc. 10th Innovations in Theoretical Computer Science Conference, San Diego, CA, USA, 2019, pp. 1:1–1:19.
Google Scholar
[35]
P. Liu, A. Rubinstein, J. Vondrák, and J. Zhao, Cardinality constrained submodular maximization for random streams, in Proc. 35th Ann. Conf. on Neural Information Processing Systems, Virtual Event, 2021, pp. 6491–6502.
Google Scholar
[36]
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, Stockholm, Sweden, 2018, pp. 3826–3835.
Google Scholar
[37]
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
[38]
Y. Wang, F. Fabbri, and M. Mathioudakis, Fair and representative subset selection from data streams, in Proc. 31st Int. Web Conferences, Ljubljana, Slovenia, 2021, pp. 1340–1350.
Crossref Google Scholar
[39]
M. Feldman, P. Liu, A. Norouzi-Fard, O. Svensson, and R. Zenklusen, Streaming submodular maximization under matroid constaints, in Proc. 49th Int. Colloquium on Automata, Languages, and Programming, Paris, France, 2022, pp. 59:1–59:20.
Google Scholar
Tsinghua Science and Technology
Volume 28 Issue 6,
December 2023
Pages 1023-1029
DOI: 10.26599/TST.2022.9010068
Cite this article:
Gong Q, Meng K, Yang R, et al. A Note on Maximizing Regularized Submodular Functions Under Streaming. Tsinghua Science and Technology, 2023, 28(6): 1023-1029. https://doi.org/10.26599/TST.2022.9010068

648

Views

54

Downloads

0

Crossref

0

Web of Science

0

Scopus

0

CSCD

Altmetrics
Received: 31 July 2022
Revised: 15 November 2022
Accepted: 21 December 2022
Published: 28 July 2023
© The author(s) 2023.

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