In this paper,we consider the k-correlation clustering problem.Given an edge-weighted graph G(V,E)where the edges are labeled either“+”(similar)or“−”(different)with nonnegative weights,we want to partition the nod...In this paper,we consider the k-correlation clustering problem.Given an edge-weighted graph G(V,E)where the edges are labeled either“+”(similar)or“−”(different)with nonnegative weights,we want to partition the nodes into at most k-clusters to maximize agreements—the total weights of“+”edges within clusters and“−”edges between clusters.This problem is NP-hard.We design an approximation algorithm with the approximation ratio{a,(2-k)a+k-1/k},where a is the weighted proportion of“+”edges in all edges.As a varies from 0 to 1,the approximation ratio varies from k-1/k to 1 and the minimum value is 1/2.展开更多
基金supported by the National Natural Science Foundation of China(Nos.11901605 and 12101069)the disciplinary funding of Central University of Finance and Economics(CUFE)+1 种基金the Emerging Interdisciplinary Project of CUFEthe Fundamental Research Funds for the Central Universities and Innovation Foundation of BUPT for Youth(No.500421358).
文摘In this paper,we consider the k-correlation clustering problem.Given an edge-weighted graph G(V,E)where the edges are labeled either“+”(similar)or“−”(different)with nonnegative weights,we want to partition the nodes into at most k-clusters to maximize agreements—the total weights of“+”edges within clusters and“−”edges between clusters.This problem is NP-hard.We design an approximation algorithm with the approximation ratio{a,(2-k)a+k-1/k},where a is the weighted proportion of“+”edges in all edges.As a varies from 0 to 1,the approximation ratio varies from k-1/k to 1 and the minimum value is 1/2.
