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
View PDF
Submit Manuscript AI Chat Paper
Show Outline
Show full outline
Hide 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


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/ε4log3(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.


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.
L. Mualem and M. Feldman, Using partial monotonicity in submodular maximization, arXiv prefprint arXiv: 2202. 03051, 2022.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
T. Soma and Y. Yoshida, Maximizing monotone submodular functions over the integer lattice, Math. Program., vol 172, nos. 1&2, pp. 539–563, 2018.
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.
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.
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.
A. Chakrabarti and S. Kale, Submodular maximization meets streaming: Matchings, matroids, and more, Math. Program., vol. 154, nos. 1&2, pp. 225–247, 2015.
M. Feldman, A. Norouzi-Fard, O. Svensson, and R. Zenklusen, Streaming submodular maximization with matroid and matching constraints, arXiv prefprint arXiv: 2107.07183, 2022.
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.
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.
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.
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.
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.
M. H. Bateni, M. Hajiaghayi, and M. Zadimoghaddam, Submodular secretary problem and extensions, ACM Trans. Algorithms, vol. 9, no. 4, p. 32, 2013.
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.
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.
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.
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.
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.
Tsinghua Science and Technology
Pages 906-915
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.








Web of Science






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 (