Correlation Clustering with Asymmetric Classification Errors

08/11/2021

∙

by   Jafar Jafarov, et al.

∙

0

∙

share

In the Correlation Clustering problem, we are given a weighted graph G with its edges labeled as "similar" or "dissimilar" by a binary classifier. The goal is to produce a clustering that minimizes the weight of "disagreements": the sum of the weights of "similar" edges across clusters and "dissimilar" edges within clusters. We study the correlation clustering problem under the following assumption: Every "similar" edge e has weight 𝐰_e∈[α𝐰, 𝐰] and every "dissimilar" edge e has weight 𝐰_e≥α𝐰 (where α≤ 1 and 𝐰>0 is a scaling parameter). We give a (3 + 2 log_e (1/α)) approximation algorithm for this problem. This assumption captures well the scenario when classification errors are asymmetric. Additionally, we show an asymptotically matching Linear Programming integrality gap of Ω(log 1/α).