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

Maximizing Submodular+Supermodular Functions Subject to a Fairness Constraint

Beijing Institute for Scientific and Engineering Computing, Beijing University of Technology, Beijing 100124, China
Faculty of Management, University of New Brunswick, Fredericton E3B 5A3, Canada
School of Mathematics and Statistics, Shandong Normal University, Jinan 250014, China
Show Author Information

Abstract

We investigate the problem of maximizing the sum of submodular and supermodular functions under a fairness constraint. This sum function is non-submodular in general. For an offline model, we introduce two approximation algorithms: A greedy algorithm and a threshold greedy algorithm. For a streaming model, we propose a one-pass streaming algorithm. We also analyze the approximation ratios of these algorithms, which all depend on the total curvature of the supermodular function. The total curvature is computable in polynomial time and widely utilized in the literature.

Keywords

submodular functionsupermodular functionfairness constraintgreedy algorithmthreshold greedy algorithmstreaming algorithm

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]
Y. Filmus and J. Ward, Monotone submodular maximization over a matroid via non-oblivious local search, SIAM J. Comput., vol. 43, no. 2, pp. 514–542, 2014.
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]
E. Balkanski, A. Rubinstein, and Y. Singer, An exponential speedup in parallel running time for submodular maximization without loss in approximation, in Proc. 30th Annu. ACM-SIAM Symp. on Discrete Algorithms, San Diego, CA, USA, 2019, pp. 283–302.
Crossref Google Scholar
[5]
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
[6]
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
[7]
Y. Yoshida, Maximizing a monotone submodular function with a bounded curvature under a knapsack constraint, SIAM J. Discrete Mathem., vol. 33, no. 3, pp. 1452–1471, 2019.
Crossref Google Scholar
[8]
M. El Halabi, S. Mitrovic, A. Norouzi-Fard, J. Tardos, and J. Tarnawski, Fairness in streaming submodular maximization: Algorithms and hardness, in Proc. 34th Conf. on Neural Information Processing Systems, Vancouver, Canada, 2020, pp. 13609–13622.
Google Scholar
[9]
Y. H. Wang, F. Fabbri, and M. Mathioudakis, Streaming submodular maximization with fairness constraints, in Proc. the Web Conf. 2021, Ljubljana, Slovenia, 2021, pp. 1340–1350.
Google Scholar
[10]
W. R. Bai and J. Bilmes, Greed is still good: Maximizing monotone submodular+supermodular (BP) functions, in Proc. 35th Int. Conf. on Machine Learning, Stockholmsmas̈san, Stockholm, Sweden, 2018, pp. 304–313.
Google Scholar
[11]
A. A. Bian, J. M. Buhmann, A. Krause, and S. Tschiatschek, Guarantees for greedy maximization of non-submodular functions with applications, in Proc. 34th Int. Conf. on Machine Learning, Sydney, Australia, 2017, pp. 498–507.
Google Scholar
[12]
A. Kuhnle, J. D. Smith, V. G. Crawford, and M. T. Thai, Fast maximization of non-submodular, monotonic functions on the integer lattice, in Proc. 35th Int. Conf. on Machine Learning, Stockholmsmas̈san, Sweden, 2018, pp. 2791–2800.
Google Scholar
[13]
T. Soma and Y. Yoshida, Maximizing monotone submodular functions over the integer lattice, Math. Program., vol. 172, nos. 12, pp. 539–563, 2018.
Crossref Google Scholar
[14]
B. Goldengorin, Maximization of submodular functions: Theory and enumeration algorithms, Eur. J. Oper. Res., vol. 198, no. 1, pp. 102–112, 2009.
Crossref Google Scholar
[15]
N. Buchbinder, M. Feldman, and R. Schwartz, Online submodular maximization with preemption, ACM Trans. Algorithms, vol. 15, no. 3, p. 30, 2019.
Crossref Google Scholar
[16]
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
[17]
S. Corbett-Davies, E. Pierson, A. Feller, S. Goel, and A. Huq, Algorithmic decision making and the cost of fairness, in Proc. 23rd ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining, Halifax, Canada, 2017, pp. 797–806.
Crossref Google Scholar
Tsinghua Science and Technology
Volume 29 Issue 1,
February 2024
Pages 46-55
DOI: 10.26599/TST.2022.9010013
Cite this article:
Zhang Z, Meng K, Du D, et al. Maximizing Submodular+Supermodular Functions Subject to a Fairness Constraint. Tsinghua Science and Technology, 2024, 29(1): 46-55. https://doi.org/10.26599/TST.2022.9010013

479

Views

53

Downloads

1

Crossref

1

Web of Science

1

Scopus

0

CSCD

Altmetrics
Received: 18 February 2022
Accepted: 20 April 2022
Published: 21 August 2023
© The author(s) 2024.

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