TY - JOUR

T1 - Approximation Algorithms for Vertex Happiness

AU - Xu, Yao

AU - Chen, Yong

AU - Zhang, Peng

AU - Goebel, Randy

N1 - Publisher Copyright:
© 2019, Operations Research Society of China, Periodicals Agency of Shanghai University, Science Press, and Springer-Verlag GmbH Germany, part of Springer Nature.

PY - 2019/9/1

Y1 - 2019/9/1

N2 - 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 Lovász 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 factor of 2 - 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- ε) -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 Lovász 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 Ω(log 2k/ k).

AB - 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 Lovász 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 factor of 2 - 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- ε) -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 Lovász 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 Ω(log 2k/ k).

KW - Approximation algorithm

KW - Integrality gap

KW - Multi-labeling

KW - Polynomial-time reduction

KW - Submodular/supermodular set function

KW - Vertex happiness

UR - http://www.scopus.com/inward/record.url?scp=85070733086&partnerID=8YFLogxK

U2 - 10.1007/s40305-019-00260-1

DO - 10.1007/s40305-019-00260-1

M3 - Article

AN - SCOPUS:85070733086

SN - 2194-668X

VL - 7

SP - 429

EP - 448

JO - Journal of the Operations Research Society of China

JF - Journal of the Operations Research Society of China

IS - 3

ER -