  Correlation Clustering is a classic clustering objective arising in numerous
machine learning and data mining applications. Given a graph $G=(V,E)$, the
goal is to partition the vertex set into clusters so as to minimize the number
of edges between clusters plus the number of edges missing within clusters. The
problem is APX-hard and the best known polynomial time approximation factor is
1.73 by Cohen-Addad, Lee, Li, and Newman [FOCS'23]. They use an LP with
$|V|^{1/\epsilon^{\Theta(1)}}$ variables for some small $\epsilon$. However,
due to the practical relevance of correlation clustering, there has also been
great interest in getting more efficient sequential and parallel algorithms.
The classic combinatorial \emph{pivot} algorithm of Ailon, Charikar and Newman
[JACM'08] provides a 3-approximation in linear time. Like most other algorithms
discussed here, this uses randomization. Recently, Behnezhad, Charikar, Ma and
Tan [FOCS'22] presented a $3+\epsilon$-approximate solution for solving problem
in a constant number of rounds in the Massively Parallel Computation (MPC)
setting. Very recently, Cao, Huang, Su [SODA'24] provided a 2.4-approximation
in a polylogarithmic number of rounds in the MPC model and in $\tilde{O}
(|E|^{1.5})$ time in the classic sequential setting. They asked whether it is
possible to get a better than 3-approximation in near-linear time?
  We resolve this problem with an efficient combinatorial algorithm providing a
drastically better approximation factor. It achieves a $\sim 2-2/13 <
1.847$-approximation in sub-linear ($\tilde O(|V|)$) sequential time or in
sub-linear ($\tilde O(|V|)$) space in the streaming setting. In the MPC model,
we give an algorithm using only a constant number of rounds that achieves a
$\sim 2-1/8 < 1.876$-approximation.
