Approximation algorithms for vertex happiness
Full Text: Xu2019_Article_ApproximationAlgorithmsForVert.pdf
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/๐ (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/๐ , 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/๐โ๐) -approximation, for any ๐>0 . For the MHV problem, the 2 / k-approximation improves the previous best approximation ratio max{1/๐,1/(๐ฅ+1/๐(๐ฅ))} , where ๐ฅ is the maximum vertex degree of the input graph and ๐(๐ฅ)=(๐ฅโพโพโ+๐ฅ+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 ๐บ(log2๐/๐) .
Citation
Y. Xu, Y. Chen, P. Zhang, R. Goebel. "Approximation algorithms for vertex happiness". Journal of Operations Research Society of China, 7(3), pp 429-448, September 2019.| Keywords: | Vertex happiness, Multi-labeling, Submodular/supermodular set function, Approximation algorithm, Polynomial-time reduction, Integrality gap |
| Category: | In Journal |
| Web Links: | DOI |
| Springer |
BibTeX
@article{Xu+al:19,
author = {Yao Xu and Yong Chen and Peng Zhang and Randy Goebel},
title = {Approximation algorithms for vertex happiness},
Volume = "7",
Number = "3",
Pages = {429-448},
journal = {Journal of Operations Research Society of China},
year = 2019,
}Last Updated: February 13, 2020Submitted by Sabina P
