@article{Ji2024, 
author = {Sai Ji and Min Li and Mei Liang and Zhenning Zhang},
title = {Robust Correlation Clustering Problem with Locally Bounded Disagreements},
year = {2024},
journal = {Tsinghua Science and Technology},
volume = {29},
number = {1},
pages = {66-75},
keywords = {approximation algorithm, min-max disagreements, outliers, penalties, LP-rounding},
url = {https://www.sciopen.com/article/10.26599/TST.2023.9010027},
doi = {10.26599/TST.2023.9010027},
abstract = {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.}
}