Maximizing Submodular+Supermodular Functions Subject to a Fairness Constraint

作     者：Zhenning Zhang Kaiqiao Meng Donglei Du Yang Zhou Zhenning Zhang;Kaiqiao Meng;Donglei Du;Yang Zhou

作者机构：Beijing Institute for Scientific and Engineering ComputingBeijing University of TechnologyBeijing 100124China Faculty of ManagementUniversity of New BrunswickFredericton E3B 5A3Canada School of Mathematics and StatisticsShandong Normal UniversityJinan 250014China 

出 版 物：《Tsinghua Science and Technology》 (清华大学学报（自然科学版（英文版）)

年 卷 期：2024年第29卷第1期

页      面：46-55页

核心收录：

学科分类：0303[法学-社会学] 12[管理学] 1204[管理学-公共管理] 03[法学] 0808[工学-电气工程] 07[理学] 030301[法学-社会学] 070104[理学-应用数学] 0835[工学-软件工程] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：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) 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) 

主　　题：submodular function supermodular function fairness constraint greedy algorithm threshold greedy algorithm streaming algorithm 

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