标题:Improved Approximation Algorithms for the Maximum Happy Vertices and Edges Problems
作者:Zhang, Peng; Jiang, Tao; Li, Angsheng
通讯作者:Zhang, Peng
作者机构:[Zhang, Peng] Shandong Univ, Sch Comp Sci & Technol, Jinan 250101, Peoples R China.; [Jiang, Tao] Univ Calif Riverside, Dept Comp Sci & Engn, Rivers 更多
会议名称:21st International Computing and Combinatorics Conference (COCOON)
会议日期:AUG 04-06, 2015
来源:COMPUTING AND COMBINATORICS
出版年:2015
卷:9198
页码:159-170
DOI:10.1007/978-3-319-21398-9_13
摘要: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/Delta+1, where Delta is the maximum vertex degree, and MHE can be approximated within 1/2 + root 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.
收录类别:CPCI-S;EI;SCOPUS
WOS核心被引频次:1
Scopus被引频次:5
资源类型:会议论文;期刊论文
原文链接:https://www.scopus.com/inward/record.uri?eid=2-s2.0-84951076933&doi=10.1007%2f978-3-319-21398-9_13&partnerID=40&md5=3eecce7e348f36319789c026cf97b5ef
TOP