Approximation and hardness results for the Max k-Uncut problem
Approximation and hardness results for the Max k-Uncut problem
复制标题
Max k-Uncut 问题的近似和硬度结果
DOI：
10.1016/j.tcs.2017.09.003
复制
发表时间：
2017-09
影响因子：
1.1
通讯作者：
Dachuan Xu
中科院分区：
文献类型：
--
作者：
Peng Zhang;Chenchen Wu;Dachuan Xu
在研究大规模复杂网络的齐次律时，我们得到了一个组合优化问题，我们称之为Max k-Uncut问题。给定一个n顶点无向图G=(V， E)，在边上定义了非负权值{w E | E∈E}，以及一个正整数k， Max k- uncut问题要求找到V的一个划分{v1， v2,⋯,vk}，使得未切割的边的总权值最大化。直观地说，未被切割的边连接两个具有相同或相似属性的顶点，因为它们位于分区的同一部分。有趣的是，Max k-Uncut问题只是经典的Min k-Cut问题的补充。对于Max k- uncut问题，我们提出了一个随机化（1−k n） 2-近似算法，一个贪婪的(1−2 (k−1)n)-近似算法，以及一个Ω (1 2 α)-近似算法，将其简化为den最k- subgraph，其中α是den最k- subgraph问题的近似比。更重要的是，我们证明了Max k-Uncut和den最k-Subgraph实际上在近似性上是等价的，其近似性可达2倍。在P≠NP的假设下，我们也证明了最大k-Uncut的近似硬度结果。
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 {w e| e∈ 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 Ω (1 2 α)-approximation algorithm by reducing it to Densest k-Subgraph, where α 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≠ NP.
登录
查看更多内容
DOI：
10.1007/978-0-387-30162-4_28
发表时间：
2021-08
期刊：
Proceedings of the 1997 International Symposium on Parallel Architectures, Algorithms and Networks (I-SPAN'97)
影响因子：
--
作者：
通讯作者：
--
影响因子：
1.1
作者：
Frieze, A;Jerrum, M
通讯作者：
Jerrum, M
DOI：
10.2307/3616070
发表时间：
1973-12
期刊：
The Mathematical Gazette
影响因子：
--
作者：
K. Fraughnaugh
通讯作者：
K. Fraughnaugh
DOI：
10.1145/276698.276711
发表时间：
1998-05
期刊：
--
影响因子：
--
作者：
G. Călinescu;H. Karloff;Y. Rabani
通讯作者：
G. Călinescu;H. Karloff;Y. Rabani
DOI：
10.1007/978-3-8348-9329-1_2
发表时间：
2010
期刊：
--
影响因子：
--
作者：
M. Loebl
通讯作者：
M. Loebl