[控场AI]
概念Capacitated Cluster Editing

容量集群编辑

一种图聚类问题,要求在团大小不超过给定上限的约束下,通过最少的边编辑(删除正边或添加负边)将符号图划分为不相交的团。该问题是NP-hard和APX-hard的,常用于计算生物学中的蛋白质复合物识别和社交网络分析。

时间轴 (近 90 天)

11月5日

容量集群编辑问题在无容量约束时是NP-hard的,且已被证明是APX-hard的。

待验证50%
11月5日

近期一篇论文提出了新的降规模技术和混合采样方法,将容量集群编辑的近似比提升至1.7537+ε。

待验证50%
11月5日

容量集群编辑问题接受一个完整的边符号图作为输入,目标是构造一组大小不超过给定k的不相交团,使得团内负边和团外正边的总数最小。

待验证50%
11月5日

论文提出了一种降规模过程,基于任意无容量问题的α-近似算法,构造出容量问题的α_k=2α+1近似算法。

待验证50%
11月5日

对于任意分数容量集群-LP解,使用普通pivoting的混合方法期望成本不超过(9/5)L + (1/10)OPT_k。

待验证50%
11月5日

对于任意分数容量集群-LP解,使用条件pivoting的混合方法期望成本不超过(306/203)L + (50/203)OPT_k。

待验证50%
11月5日

论文借助García-Soriano和Schohn的近似对偶分离框架的基数约束适应版,获得了所需的分数解,并分别得到随机化(1.9+ε)-近似算法和随机化(1.7537+ε)-近似算法。

待验证50%
11月5日

容量集群编辑在生物信息学(如蛋白质复合物识别)和社交网络分析(如社区发现)中具有广泛应用。

待验证50%

全部知识事实 (8)

来源文章