A Note on Maximizing Regularized Submodular Functions Under Streaming

Qinqin Gong; Kaiqiao Meng; Ruiqi Yang; Zhenning Zhang

doi:10.26599/TST.2022.9010068

Tsinghua Science and Technology 2023, 28(6): 1023-1029 https://doi.org/10.26599/TST.2022.9010068

Open Access | Issue | Published: 28 July 2023

A Note on Maximizing Regularized Submodular Functions Under Streaming

Show Author's Information Hide Author's Information Qinqin Gong^¹, Kaiqiao Meng^¹, Ruiqi Yang^¹(

), Zhenning Zhang^¹

1Beijing Institute for Scientific and Engineering Computing, Beijing University of Technology, Beijing 100124, China

Keywords:

threshold technique, submodular optimization, regular model, streaming algorithms

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

Download citation

EndNote(RIS)

BibTeX

378

Views

Downloads

Citations

Crossref

WoS

Scopus

CSCD

Abstract Full text About this article

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.

Full text

Abstract

Full text

Outline

About this article

A Note on Maximizing Regularized Submodular Functions Under Streaming

Show Author's information Hide Author's Information Qinqin Gong^¹, Kaiqiao Meng^¹, Ruiqi Yang^¹(

), Zhenning Zhang^¹

1Beijing Institute for Scientific and Engineering Computing, Beijing University of Technology, Beijing 100124, China

Abstract

Keywords: threshold technique, submodular optimization, regular model, streaming algorithms

References(39)

[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.

DOI Google Scholar

[2]

N. Buchbinder, M. Feldman, J. Naor, and R. Schwartz, Submodular maximization with cardinality constraints, in Proc. 25^th Ann. ACM-SIAM Symp. on Discrete Algorithms, Portland, OR, USA, 2014, pp. 1433–1452.

DOI 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.

DOI Google Scholar

[4]

Y. Filmus and J. Ward, A tight combinatorial algorithm for submodular maximization subject to a matroid constraint, in Proc. 53^rd IEEE Ann. Symp. on Foundations of Computer Science, New Brunswick, NJ, USA, 2012, pp. 659–668.

DOI Google Scholar

[5]

N. Buchbinder, M. Feldman, and M. Garg, Deterministic (1/2+ϵ)-approximation for submodular maximization over a matroid, in Proc. 30^th Ann. ACM-SIAM Symp. on Discrete Algorithms, San Diego, CA, USA, 2019, pp. 241–254.

DOI Google Scholar

[6]

A. Badanidiyuru, A. Karbasi, E. Kazemi, and J. Vondrák, Submodular maximization through barrier functions, in Proc. 34^th 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. 38^th 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. 30^th 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. 6^th Int. Workshop on Internet and Network Economics, Stanford, CA, USA, 2010, pp. 246–257.

DOI Google Scholar

[10]

M. Feldman, Guess free maximization of submodular and linear sums, Algorithmica, vol. 83, no. 3, pp. 853–878, 2021.

DOI Google Scholar

[11]

C. Harshaw, M. Feldman, J. Ward, and A. Karbasi, Submodular maximization beyond non-negativity: Guarantees, fast algorithms, and applications, in Proc. 36^th 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.

DOI 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.

DOI Google Scholar

[14]

Z. Abbassi, V. S. Mirrokni, and M. Thakur, Diversity maximization under matroid constraints, in Proc. 19^th ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining, Chicago, IL, USA, 2013, pp. 32–40.

DOI 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.

DOI Google Scholar

[16]

U. Feige, A threshold of ln⁡n for approximating set cover, J. ACM, vol. 45, no. 4, pp. 634–652, 1998.

DOI Google Scholar

[17]

C. Lu, W. Yang, and S. Gao, Regularized non-monotone submodular maximization, Optimization, , 2022.

DOI 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.

DOI 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.

DOI Google Scholar

[20]

S. Tang and J. Yuan, Adaptive regularized submodular maximization, in Proc. 32^nd 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.

DOI Google Scholar

[22]

A. Badanidiyuru, B. Mirzasoleiman, A. Karbasi, and A. Krause, Streaming submodular maximization: Massive data summarization on the fly, in Proc. 20^th ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining, New York, NY, USA, 2014, pp. 671–680.

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. 36^th 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. 31^st 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.

DOI 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.

DOI Google Scholar

[27]

C. Chekuri, S. Gupta, and K. Quanrud, Streaming algorithms for submodular function maximization, in Proc. 42^nd Int. Colloquium on Automata, Languages, and Programming, Kyoto, Japan, 2015, pp. 318–330.

DOI Google Scholar

[28]

M. Feldman, A. Karbasi, and E. Kazemi, Do less, get more: Streaming submodular maximization with subsampling, in Proc. 32^nd 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. 37^th 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.

DOI Google Scholar

[31]

R. Levin and D. Wajc, Streaming submodular matching meets the primal-dual method, in Proc. 32^nd ACM-SIAM Symp. on Discrete Algorithms, Alexandria, VA, USA, 2021, pp. 1914–1933.

DOI 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. 25^th Int. Workshop on Randomization and Computation (RANDOM 2021) and 24^th 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. 22^nd Int. Conf. on Integer Programming and Combinatorial Optimization, Atlanta, GA, USA, 2021, pp. 208–222.

DOI Google Scholar

[34]

S. Agrawal, M. Shadravan, and C. Stein, Submodular secretary problem with shortlists, in Proc. 10^th 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. 35^th 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. 35^th 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. 38^th 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. 31^st Int. Web Conferences, Ljubljana, Slovenia, 2021, pp. 1340–1350.

DOI Google Scholar

[39]

M. Feldman, P. Liu, A. Norouzi-Fard, O. Svensson, and R. Zenklusen, Streaming submodular maximization under matroid constaints, in Proc. 49^th Int. Colloquium on Automata, Languages, and Programming, Paris, France, 2022, pp. 59:1–59:20.

Google Scholar

About this article

Publication history

Acknowledgements

Rights and permissions

Publication history

Received: 31 July 2022

Revised: 15 November 2022

Accepted: 21 December 2022

Published: 28 July 2023

Issue date: December 2023

Copyright

Acknowledgements

This work was supported by the Beijing Natural Science Foundation Project (No. Z200002), the National Natural Science Foundation of China (Nos. 12001523, 12131003, and 12101587), the National Innovation and Entrepreneurship Training Program for College Students of Beijing University of Technology (No. GJDC-2022-01-39), 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/).