  This paper considers correlation clustering on unweighted complete graphs. We
give a combinatorial algorithm that returns a single clustering solution that
is simultaneously $O(1)$-approximate for all $\ell_p$-norms of the disagreement
vector; in other words, a combinatorial $O(1)$-approximation of the all-norms
objective for correlation clustering. This is the first proof that minimal
sacrifice is needed in order to optimize different norms of the disagreement
vector. In addition, our algorithm is the first combinatorial approximation
algorithm for the $\ell_2$-norm objective, and more generally the first
combinatorial algorithm for the $\ell_p$-norm objective when $1 < p < \infty$.
It is also faster than all previous algorithms that minimize the $\ell_p$-norm
of the disagreement vector, with run-time $O(n^\omega)$, where $O(n^\omega)$ is
the time for matrix multiplication on $n \times n$ matrices. When the maximum
positive degree in the graph is at most $\Delta$, this can be improved to a
run-time of $O(n\Delta^2 \log n)$.
