Robust Correlation Clustering Problem with Locally Bounded Disagreements

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\mathrm{=}\mathrm{(}V\mathrm{,}E\mathrm{)}$, each edge in the graph is marked by a positive label " $\mathrm{+}$" or a negative label " $\mathrm{-}$" 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 $\delta \mathrm{\in }\mathrm{(}\mathrm{0}\mathrm{,}\mathrm{1}\mathrm{/}\mathrm{14}\mathrm{)}$, we first provide a threshold-based iterative clustering algorithm based on LP-rounding technique, which is a $\mathrm{(}\mathrm{1}\mathrm{/}\delta \mathrm{,}\mathrm{7}\mathrm{/}\mathrm{(}\mathrm{1}\mathrm{-}\mathrm{14}\mathsf{}\delta \mathrm{)}\mathrm{)}$-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 $\mathrm{21}$ for min-max disagreements with penalties when we set parameter $\delta \mathrm{=}\mathrm{1}\mathrm{/}\mathrm{21}$.