  Correlation clustering is a fundamental combinatorial optimization problem
arising in many contexts and applications that has been the subject of dozens
of papers in the literature. In this problem we are given a general weighted
graph where each edge is labeled positive or negative. The goal is to obtain a
partitioning (clustering) of the vertices that minimizes disagreements - weight
of negative edges trapped inside a cluster plus positive edges between
different clusters. Most of the papers on this topic mainly focus on minimizing
total disagreement, a global objective for this problem. In this paper, we
study a cluster-wise objective function that asks to minimize the maximum
number of disagreements of each cluster, which we call min-max correlation
clustering. The min-max objective is a natural objective that respects the
quality of every cluster. In this paper, we provide the first nontrivial
approximation algorithm for this problem achieving an $\mathcal{O}(\sqrt{\log
n\cdot\max\{\log(|E^-|),\log(k)\}})$ approximation for general weighted graphs,
where $|E^-|$ denotes the number of negative edges and $k$ is the number of
clusters in the optimum solution. To do so, we also obtain a corresponding
result for multicut where we wish to find a multicut solution while trying to
minimize the total weight of cut edges on every component. The results are then
further improved to obtain (i) $\mathcal{O}(r^2)$-approximation for min-max
correlation clustering and min-max multicut for graphs that exclude $K_{r,r}$
minors (ii) a 14-approximation for the min-max correlation clustering on
complete graphs.
