标题:Approximation and hardness results for the Max k-Uncut problem
作者:Zhang, Peng; Wu, Chenchen; Xu, Dachuan
通讯作者:Xu, DC;Xu, Dachuan
作者机构:[Zhang, Peng] Shandong Univ, Sch Comp Sci & Technol, Jinan 250101, Shandong, Peoples R China.; [Wu, Chenchen] Tianjin Univ Technol, Coll Sci, Tianji 更多
会议名称:10th Annual International Conference on Combinatorial Optimization and Applications (COCOA)
会议日期:DEC 16-18, 2016
来源:THEORETICAL COMPUTER SCIENCE
出版年:2018
卷:749
页码:47-58
DOI:10.1016/j.tcs.2017.09.003
关键词:Max k-Uncut; Densest k-Subgraph; Homophily; Approximation algorithm;; Computational complexity
摘要:In the study of the homophily law of large scale complex networks, we get a combinatorial optimization problem which we call the Max k-Uncut problem. Given an n-vertex undirected graph G = (V, E) with nonnegative weights {we vertical bar e is an element of E} defined on edges, and a positive integer k, the Max k-Uncut problem asks to find a partition (V-1, V-2, ..., V-k} of V such that the total weight of edges that are not cut is maximized. Intuitively, an edge that is not cut connects two vertices with the same or similar attributes since they are in the same part of the partition. Interestingly, the Max k-Uncut problem is just the complement of the classic Min k-Cut problem. For Max k-Uncut, we present a randomized (1 - k/n)(2)-approximation algorithm, a greedy (1 - 2(k - 1/n) approximation algorithm, and an Omega(1/2 alpha)-approximation algorithm by reducing it to Densest k-Subgraph, where alpha is the approximation ratio of the Densest k-Subgraph problem. More importantly, we show that Max k-Uncut and Densest k-Subgraph are in fact equivalent in approximability up to a factor of 2. We also prove an approximation hardness result for Max k-Uncut under the assumption P not equal NP. (C) 2017 Elsevier B.V. All rights reserved.
收录类别:CPCI-S;EI;SCIE
资源类型:会议论文;期刊论文
TOP