TY - GEN
T1 - Improved approximation algorithms for the maximum happy vertices and edges problems
AU - Zhang, Peng
AU - Jiang, Tao
AU - Li, Angsheng
N1 - Publisher Copyright:
© Springer International Publishing Switzerland 2015.
PY - 2015
Y1 - 2015
N2 - The Maximum Happy Vertices (MHV) problem and the Maximum Happy Edges (MHE) problem are two fundamental problems arising in the study of the homophyly phenomenon in large scale networks. Both of these two problems are NP-hard. Interestingly, the MHE problem is a natural generalization of Multiway Uncut, the complement of the classic Multiway Cut problem. In this paper, we present new approximation algorithms for MHV and MHE based on randomized LP-rounding techniques. Specifically, we show that MHV can be approximated within 1/Δ+1, where Δ is the maximum vertex degree, and MHE can be approximated within 1/2 + √2/4 f(k) ≥ 0.8535, where f(k) ≥ 1 is a function of the color number k. These results improve on the previous approximation ratios for MHV, MHE as well as Multiway Uncut in the literature.
AB - The Maximum Happy Vertices (MHV) problem and the Maximum Happy Edges (MHE) problem are two fundamental problems arising in the study of the homophyly phenomenon in large scale networks. Both of these two problems are NP-hard. Interestingly, the MHE problem is a natural generalization of Multiway Uncut, the complement of the classic Multiway Cut problem. In this paper, we present new approximation algorithms for MHV and MHE based on randomized LP-rounding techniques. Specifically, we show that MHV can be approximated within 1/Δ+1, where Δ is the maximum vertex degree, and MHE can be approximated within 1/2 + √2/4 f(k) ≥ 0.8535, where f(k) ≥ 1 is a function of the color number k. These results improve on the previous approximation ratios for MHV, MHE as well as Multiway Uncut in the literature.
UR - https://www.scopus.com/pages/publications/84951076933
U2 - 10.1007/978-3-319-21398-9_13
DO - 10.1007/978-3-319-21398-9_13
M3 - 会议稿件
AN - SCOPUS:84951076933
SN - 9783319213972
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 159
EP - 170
BT - Computing and Combinatorics - 21st International Conference, COCOON 2015, Proceedings
A2 - Xu, Dachuan
A2 - Du, Donglei
A2 - Du, Dingzhu
PB - Springer Verlag
T2 - 21st International Conference on Computing and Combinatorics Conference, COCOON 2015
Y2 - 4 August 2015 through 6 August 2015
ER -