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

Approximating (mB,mP⁢)-Monotone BP Maximization and Extensions

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
School of Science, Beijing University of Posts and Telecommunications, Beijing 100876, China
Show Author Information

Abstract

The paper proposes the optimization problem of maximizing the sum of suBmodular and suPermodular (BP) functions with partial monotonicity under a streaming fashion. In this model, elements are randomly released from the stream and the utility is encoded by the sum of partial monotone suBmodular and suPermodular functions. The goal is to determine whether a subset from the stream of size bounded by parameter k subject to the summarized utility is as large as possible. In this work, a threshold-based streaming algorithm is presented for the BP maximization that attains a ((1-κ)/(2-κ)-𝒪⁢(ε))-approximation with 𝒪⁢(1/ε4⁢log3⁡(1/ε)⁢log⁡((2-κ)⁢k/(1-κ)2)) memory complexity, where κ denotes the parameter of supermodularity ratio. We further consider a more general model with fair constraints and present a greedy-based algorithm that obtains the same approximation. We finally investigate this fair model under the streaming fashion and provide a ((1-κ)4/(2-2⁢κ+κ2)2-𝒪⁢(ε))-approximation algorithm.

Keywords

approximation algorithmsubmodular maximizationstreaming modelthreshold technique

References

[1]
R. Yang, S. Gao, L. Han, G. Li, and Z. Zhao, Approximating BP maximization with distorted-based strategy, in Proc. 22nd Int. Conf. on Parallel and Distributed Computing: Applications and Technologies, Guangzhou, China, 2022, pp. 452–459.
Crossref Google Scholar
[2]
L. Mualem and M. Feldman, Using partial monotonicity in submodular maximization, arXiv prefprint arXiv: 2202. 03051, 2022.
Google Scholar
[3]
W. Bai and J. Bilmes, Greed is still good: Maximizing monotone submodular + supermodular (BP) functions, in Proc. 35th Int. Conf. on Machine Learning, Stockholm, Sweden, 2018, pp. 304–313.
Google Scholar
[4]
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
[5]
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
[6]
R. Gomes and A. Krause, Budgeted nonparametric learning from data streams, in Proc. 27th Int. Conf. on Machine Learning, Haifa, Israel, 2010, pp. 391–398.
Google Scholar
[7]
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
[8]
B. Mirzasoleiman, A. Badanidiyuru, and A. Karbasi, Fast constrained submodular maximization: Personalized data summarization, in Proc. 33rd Int. Conf. on Machine Learning, New York City, NY, USA, 2016, pp. 1358–1367.
Google Scholar
[9]
A. Norouzi-Fard, J. Tarnawski, S. Mitrović, 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. 3829–3838.
Google Scholar
[10]
N. Buchbinder, M. Feldman, and R. Schwartz, Online submodular maximization with preemption, in Proc. 26th Ann. ACM-SIAM Symp. on Discrete Algorithms, San Diego, CA, USA, 2015, pp. 1202–1216.
Crossref Google Scholar
[11]
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
[12]
Z. Liu, H. Chang, D. Du, and X. Zhang, Improved algorithms for non-submodular function maximization problem, Theor. Comput. Sci., vol. 931, pp. 49–55, 2022.
Crossref Google Scholar
[13]
Z. Liu, L. Guo, D. Du, D. Xu, and X. Zhang, Maximization problems of balancing submodular relevance and supermodular diversity, J. Glob. Optim., vol. 82, no. 1, pp. 179–194, 2022.
Crossref Google Scholar
[14]
A. Kuhnle, J. D. Smith, V. Crawford, and M. Thai, Fast maximization of non-submodular, monotonic functions on the integer lattice, in Proc. 35th Int. Conf. on Machine Learning, Stockholm, Sweden, 2018, pp. 2786–2795.
Google Scholar
[15]
T. Soma, N. Kakimura, K. Inaba, and K. Kawarabayashi, Optimal budget allocation: Theoretical guarantee and efficient algorithm, in Proc. 31st Int. Conf. on Machine Learning, Beijing, China, 2014, pp. 351–359.
Google Scholar
[16]
T. Soma and Y. Yoshida, Maximizing monotone submodular functions over the integer lattice, Math. Program., vol 172, nos. 1&2, pp. 539–563, 2018.
Crossref Google Scholar
[17]
Z. Zhang, D. Du, Y. Jiang, and C. Wu, Maximizing DR-submodular + supermodular functions on the integer lattice subject to a cardinality constraint, J, Glob. Optim., vol. 80, no. 3, pp. 595–616, 2021.
Crossref Google Scholar
[18]
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
[19]
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
[20]
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
[21]
M. Feldman, A. Norouzi-Fard, O. Svensson, and R. Zenklusen, Streaming submodular maximization with matroid and matching constraints, arXiv prefprint arXiv: 2107.07183, 2022.
Google Scholar
[22]
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
[23]
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, Vienna, Austria, 2020, pp. 3939–3949.
Google Scholar
[24]
B. Mirzasoleiman, S. Jegelka, and A. Krause, Streaming non-monotone submodular maximization: Personalized video summarization on the fly, in Proc. 32nd AAAI Conf. Artificial Intelligence and 30th Innovative Applications of Artificial Intelligence Conf. and 8th AAAI Symp. Educational Advances in Artificial Intelligence, New Orleans, LA, USA, 2018, pp. 1379–1386.
Crossref Google Scholar
[25]
C. C. Huang, and N. Kakimura, Multi-pass streaming algorithms for monotone submodular function maximization, Theory Comput. Syst., vol. 66, no. 1, pp. 354–394, 2022.
Crossref Google Scholar
[26]
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
[27]
M. H. Bateni, M. Hajiaghayi, and M. Zadimoghaddam, Submodular secretary problem and extensions, ACM Trans. Algorithms, vol. 9, no. 4, p. 32, 2013.
Crossref Google Scholar
[28]
N. Buchbinder, M. Feldman, Y. Filmus, and M. Garg, Online submodular maximization: Beating 1/2 made simple, Math. Program., vol. 183, nos. 1&2, pp. 149–169, 2020.
Crossref Google Scholar
[29]
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
[30]
Z. Liu, L. Chen, H. Chang, D. Du, and X. Zhang, Online algorithms for BP functions maximization, Theor. Comput. Sci., vol. 858, pp. 114–121, 2021.
Crossref Google Scholar
[31]
M. Conforti and G. Cornuéjols, Submodular set functions, matroids and the greedy algorithm: tight worst case bounds and some generalizations of the Rado-Edmonds theorem, Discrete Appl. Math., vol. 7, no. 3, pp. 251–274, 1984.
Crossref Google Scholar
[32]
M. EI. Halabi, S. Mitrovi, A. Norouzi-Fard, J. Tardos, and J. Tarnawski, Fairness in streaming submodular maximization: Algorithms and hardness, in Proc. 34th Int. Conf. Neural Information Processing Systems, Vancouver, Canada, 2020, pp. 13609–13622.
Google Scholar
Tsinghua Science and Technology
Volume 28 Issue 5,
October 2023
Pages 906-915
DOI: 10.26599/TST.2022.9010033
Cite this article:
Yang R, Gao S, Han L, et al. Approximating (mB,mP⁢)-Monotone BP Maximization and Extensions. Tsinghua Science and Technology, 2023, 28(5): 906-915. https://doi.org/10.26599/TST.2022.9010033

584

Views

34

Downloads

0

Crossref

0

Web of Science

0

Scopus

0

CSCD

Altmetrics
Received: 29 April 2022
Revised: 17 July 2022
Accepted: 22 August 2022
Published: 19 May 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