Journal Home > Volume 28 , Issue 5

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.


menu
Abstract
Full text
Outline
About this article

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

Show Author's information Ruiqi Yang1Suixiang Gao2Lu Han3Gaidi Li1( )Zhongrui Zhao1
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

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/ε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.

Keywords: approximation algorithm, submodular maximization, streaming model, threshold technique

References(32)

[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.
[2]
L. Mualem and M. Feldman, Using partial monotonicity in submodular maximization, arXiv prefprint arXiv: 2202. 03051, 2022.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[27]
M. H. Bateni, M. Hajiaghayi, and M. Zadimoghaddam, Submodular secretary problem and extensions, ACM Trans. Algorithms, vol. 9, no. 4, p. 32, 2013.
[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.
[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.
[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.
[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.
[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.
Publication history
Copyright
Acknowledgements
Rights and permissions

Publication history

Received: 29 April 2022
Revised: 17 July 2022
Accepted: 22 August 2022
Published: 19 May 2023
Issue date: October 2023

Copyright

© The author(s) 2023.

Acknowledgements

This work was supported by the National Natural Science Foundation of China (No. 12101587), the China Postdoctoral Science Foundation (No. 2022M720329), the National Natural Science Foundation of China (No. 12001523), the Beijing Natural Science Foundation Project (No. Z200002), and the National Natural Science Foundation of China (No. 12131003).

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/).

Return