Breaking 3-Factor Approximation for Correlation Clustering in
  Polylogarithmic Rounds
Nairen Cao Shang-En Huang Hsin-Hao Su
In this paper, we study parallel algorithms for the correlation clustering
problem, where every pair of two different entities is labeled with similar or
dissimilar. The goal is to partition the entities into clusters to minimize the
number of disagreements with the labels. Currently, all efficient parallel
algorithms have an approximation ratio of at least 3. In comparison with the
$1.994+\epsilon$ ratio achieved by polynomial-time sequential algorithms
[CLN22], a significant gap exists.
  We propose the first poly-logarithmic depth parallel algorithm that achieves
a better approximation ratio than 3. Specifically, our algorithm computes a
$(2.4+\epsilon)$-approximate solution and uses $\tilde{O}(m^{1.5})$ work.
Additionally, it can be translated into a $\tilde{O}(m^{1.5})$-time sequential
algorithm and a poly-logarithmic rounds sublinear-memory MPC algorithm with
$\tilde{O}(m^{1.5})$ total memory.
  Our approach is inspired by Awerbuch, Khandekar, and Rao's [AKR12]
length-constrained multi-commodity flow algorithm, where we develop an
efficient parallel algorithm to solve a truncated correlation clustering linear
program of Charikar, Guruswami, and Wirth [CGW05]. Then we show the solution of
the truncated linear program can be rounded with a factor of at most 2.4 loss
by using the framework of [CMSY15]. Such a rounding framework can then be
implemented using parallel pivot-based approaches.