Approximation Algorithms for Vertex Happiness  

作　　者：Yao Xu Yong Chen Peng Zhang Randy Goebel 

机构地区：[1]Department of Computing Science,University of Alberta,Edmonton,AB T6G 2E8,Canada [2]Department of Mathematics,Hangzhou Dianzi University,Hangzhou 310018,China [3]School of Computer Science and Technology,Shandong University,Jinan 250101,China

出　　处：《Journal of the Operations Research Society of China》2019年第3期429-448,共20页中国运筹学会会刊（英文）

基　　金：the National Natural Science Foundation of China(Nos.11771114,11571252,and 61672323);the China Scholarship Council(No.201508330054);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).

关 键 词：Vertex happiness Multi-labeling Submodular/supermodular set function Approximation algorithm Polynomial-time reduction Integrality gap 

分 类 号：O15[理学—数学]