TY  - JOUR
AU  - Ji, Sai
AU  - Li, Min
AU  - Liang, Mei
AU  - Zhang, Zhenning
PY  - 2024
TI  - Robust Correlation Clustering Problem with Locally Bounded Disagreements
JO  - Tsinghua Science and Technology
SN  - 1007-0214
SP  - 66
EP  - 75
VL  - 29
IS  - 1
AB  - Min-max disagreements are an important generalization of the correlation clustering problem (CorCP). It can be defined as follows. Given a marked complete graph  G=(V,E), each edge in the graph is marked by a positive label " +" or a negative label " -" based on the similarity of the connected vertices. The goal is to find a clustering  𝒞 of vertices  V, so as to minimize the number of disagreements at the vertex with the most disagreements. Here, the disagreements are the positive cut edges and the negative non-cut edges produced by clustering  𝒞. This paper considers two robust min-max disagreements: min-max disagreements with outliers and min-max disagreements with penalties. Given parameter  δ∈(0,1/14), we first provide a threshold-based iterative clustering algorithm based on LP-rounding technique, which is a  (1/δ,7/(1-14⁢δ))-bi-criteria approximation algorithm for both the min-max disagreements with outliers and the min-max disagreements with outliers on one-sided complete bipartite graphs. Next, we verify that the above algorithm can achieve an approximation ratio of  21 for min-max disagreements with penalties when we set parameter  δ=1/21.
UR  - https://doi.org/10.26599/TST.2023.9010027
DO  - 10.26599/TST.2023.9010027