Journal Home > Volume 29 , Issue 1
Tsinghua Science and Technology 2024, 29(1): 46-55 https://doi.org/10.26599/TST.2022.9010013
Open Access | Issue | Published: 21 August 2023

Maximizing Submodular+Supermodular Functions Subject to a Fairness Constraint

Show Author's Information Zhenning Zhang1,  Kaiqiao Meng1,  Donglei Du2,  Yang Zhou3( )
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
Keywords:
submodular function, greedy algorithm, streaming algorithm, supermodular function, fairness constraint, threshold greedy algorithm
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
Download citation
EndNote(RIS)
BibTeX

201

Views

35

Downloads

Citations

1

Crossref

1

WoS

1

Scopus

0

CSCD

Abstract Full text About this article

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.


menu
Abstract
Full text
Outline
About this article

Maximizing Submodular+Supermodular Functions Subject to a Fairness Constraint

Show Author's information Zhenning Zhang1, Kaiqiao Meng1, Donglei Du2, Yang Zhou3( )
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

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 function, greedy algorithm, streaming algorithm, supermodular function, fairness constraint, threshold greedy algorithm

References(17)

[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]
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.
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]
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.
DOI 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.
DOI 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.
DOI 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.
DOI 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.
DOI 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.
DOI 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.
DOI 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.
DOI 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.
DOI Google Scholar
Publication history
Copyright
Acknowledgements
Rights and permissions

Publication history

Received: 18 February 2022
Accepted: 20 April 2022
Published: 21 August 2023
Issue date: February 2024

Copyright

© The author(s) 2024.

Acknowledgements

The first author was supported by the National Natural Science Foundation of China (Nos. 12001025 and 12131003). The second author was supported by the Spark Fund of Beijing University of Technology (No. XH-2021-06-03). The third author was supported by the Natural Sciences and Engineering Research Council of Canada (No. 283106) and the Natural Science Foundation of China (Nos. 11771386 and 11728104). The fourth author is supported by the National Natural Science Foundation of China (No. 12001335).

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