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 ...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.展开更多
We investigate the maximum happy vertices(MHV)problem and its complement,the minimum unhappy vertices(MUHV)problem.In order to design better approximation algorithms,we introduce the supermodular and submodular multi-...We investigate the maximum happy vertices(MHV)problem and its complement,the minimum unhappy vertices(MUHV)problem.In order to design better approximation algorithms,we introduce the supermodular and submodular multi-labeling(SUP-ML and SUB-ML)problems and show that MHV and MUHV are special cases of SUP-ML and SUB-ML,respectively,by rewriting the objective functions as set functions.The convex relaxation on the I ovasz extension,originally presented for the submodular multi-partitioning problem,can be extended for the SUB-ML problem,thereby proving that SUB-ML(SUP-ML,respectively)can be approximated within a factorof2-2/k(2/k,respectively),where k is the number of labels.These general results imply that MHV and MUHV can also be approximated within factors of 2/k and 2-2/k,respectively,using the same approximation algorithms.For the MUHV problem,we also show that it is approximation-equivalent to the hypergraph multiway cut problem;thus,MUHV is Unique Games-hard to achieve a(2-2/k-e)-approximation,for anyε>0.For the MHV problem,the 2/k-approximation improves the previous best approximation ratio max{1/k,1/(△+1/g(△)},where△is the maximum vertex degree of the input graph and g(△)=(√△+√△+1)2△>4△2.We also show that an existing LP relaxation for MHV is the same as the concave relaxation on the Lovasz extension for SUP-ML;we then prove an upper bound of 2/k on the integrality gap of this LP relaxation,which suggests that the 2/k-approximation is the best possible based on this LP relaxation.Lastly,we prove that it is Unique Games-hard to approximate the MHV problem within a factor of S2(log2 k/k).展开更多
基金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)+2 种基金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).
文摘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.
基金the National Natural Science Foundation of China(Nos.11771114,11571252,and 61672323)the China Scholarship Council(No.201508330054)+1 种基金the Natural Science Foundation of Shandong Province(No.ZR2016AM28)the Natural Sciences and Engineering Research Council of Canada.
文摘We investigate the maximum happy vertices(MHV)problem and its complement,the minimum unhappy vertices(MUHV)problem.In order to design better approximation algorithms,we introduce the supermodular and submodular multi-labeling(SUP-ML and SUB-ML)problems and show that MHV and MUHV are special cases of SUP-ML and SUB-ML,respectively,by rewriting the objective functions as set functions.The convex relaxation on the I ovasz extension,originally presented for the submodular multi-partitioning problem,can be extended for the SUB-ML problem,thereby proving that SUB-ML(SUP-ML,respectively)can be approximated within a factorof2-2/k(2/k,respectively),where k is the number of labels.These general results imply that MHV and MUHV can also be approximated within factors of 2/k and 2-2/k,respectively,using the same approximation algorithms.For the MUHV problem,we also show that it is approximation-equivalent to the hypergraph multiway cut problem;thus,MUHV is Unique Games-hard to achieve a(2-2/k-e)-approximation,for anyε>0.For the MHV problem,the 2/k-approximation improves the previous best approximation ratio max{1/k,1/(△+1/g(△)},where△is the maximum vertex degree of the input graph and g(△)=(√△+√△+1)2△>4△2.We also show that an existing LP relaxation for MHV is the same as the concave relaxation on the Lovasz extension for SUP-ML;we then prove an upper bound of 2/k on the integrality gap of this LP relaxation,which suggests that the 2/k-approximation is the best possible based on this LP relaxation.Lastly,we prove that it is Unique Games-hard to approximate the MHV problem within a factor of S2(log2 k/k).
