T}z_{S}\cdot z_{S^{\prime}}\cdot a(S)\cdot a(S^{\prime})$
$\displaystyle=\sum_{S\supseteq T,S^{\prime}\supseteq
T}z_{S}z_{S^{\prime}}\left(\frac{1}{2}a^{2}(S)+\frac{1}{2}a^{2}(S^{\prime})-a(S)a(S^{\prime})\right)\geq
0.$

The first inequlaity used that $\sum_{S^{\prime}\supseteq T}z_{S^{\prime}}\leq
1$ as $T\neq\emptyset$. Therefore, $M$ is PSD. ∎

Lemma 56 places a significant constraint on the distribution of triangles. We
want to mention that the covariance matrix is implied by cluster LP, so we do
not need to add extra constraints to the linear programming.

To leverage the property of the covariance matrix being positive semi-definite
(PSD), we begin by partitioning the interval $[0,1]$ into numerous sub-
intervals denoted as $I_{1},I_{2},...,I_{t}$ and each sub-interval
$I_{j}\in[0,1]$ is continuous. Given any $y_{uv}\in[0,1]$, we use $I(y_{uv})$
to represent the interval containing $y_{uv}$. Let $l(I_{j})$ and $r(I_{j})$
be the left and right boundary of interval $I_{j}$. Given a node $u$, consider
the matrix $Q_{u}\in\mathbb{R}^{t\times t}$, where $Q_{u}(I_{j},I_{k})$ is
defined as

$Q_{u}(I_{j},I_{k})=\sum_{\begin{subarray}{c}y_{uv}\in I_{j},y_{uw}\in
I_{k}\\\ v\in V,w\in V\end{subarray}}y_{uvw}-y_{uv}y_{uw}$

When $v=u$ or $w=u$, we have $y_{uvw}-y_{uv}y_{uw}=0$ and $Q_{u}$ remains
well-defined. We first show that $Q_{u}$ is also PSD.

######  Lemma 57.

Let $Q_{u}$ be the matrix defined above, then $Q_{u}\succeq 0$.

###### Proof.

For any given vector $a\in\mathbb{R}^{t}$, let $a(I_{j})$ be the value for
index $I_{j}$.

$\displaystyle a^{\intercal}\cdot Q_{u}\cdot a$
$\displaystyle=\sum_{I_{j},I_{k}}a(I_{j})Q_{u}(I_{j},I_{k})a(I_{k})$
$\displaystyle=\sum_{I_{j},I_{k}}\sum_{y_{uv}\in I_{j},y_{uw}\in
I_{k}}a(I_{j})a(I_{k})(y_{uvw}-y_{uv}y_{uw})$
$\displaystyle=\sum_{v,w}\sum_{I_{j}\ni y_{uv},I_{k}\ni
y_{uw}}a(I_{j})a(I_{k})(y_{uvw}-y_{uv}y_{uw})$
$\displaystyle=\sum_{v,w}\sum_{y_{uv},y_{uw}}a(I(y_{uv}))a(I({y_{uw}}))(y_{uvw}-y_{uv}y_{uw})$
$\displaystyle=b^{T}\cdot COV_{u}\cdot b\geq 0$

where $b\in\mathbb{R}^{n}$ and each entry of $b$ is defined as
$b(v)=a(I(y_{uv}))$. The last inequality is using the fact that the covariance
matrix is PSD. ∎

Given a cluster LP solution $y$, let $Q(y)=\sum_{u}Q_{u}$ be the sum of
$Q_{u}$ for all vertices $u$ in the set $V$. According to Lemma 57, we can
assert that $Q(y)\succeq 0$.

We can now express the matrix $Q(y)$ using triangles $T\in\mathcal{T}$ and the
corresponding counts $\eta_{T}(y)$. To achieve this, we need to consider the
increase caused by $T$ in the matrices $Q_{u}$, $Q_{v}$, and $Q_{w}$.

Specifically, a non-degenerate triangle $T$ increases the entries
$Q_{u}(I(y_{uv}),I(y_{uw}))$ and $Q_{u}(I(y_{uw}),I(y_{uv}))$ by
$y_{uvw}-y_{uv}y_{uw}$ for the matrix $Q_{u}$,. Similar computations are
performed for $Q_{v}$ and $Q_{w}$. For degenerate triangle
$T=(y_{uv},y_{uv},1,y_{uv})$, it increases $Q_{u}(I(y_{uv}),I(y_{uv}))$ by
$(y_{uv}-y_{uv}^{2})$, increases $Q_{v}(I(y_{uv}),I(y_{uv}))$ by
$(y_{uv}-y_{uv}^{2})$ and doesn’t affect and $Q_{w}$. In either case, we
increase $Q(I(y_{uv}),I(y_{uw}))$ and $Q_{u}(I(y_{uw}),I(y_{uv}))$ by
$y_{uvw}-y_{uv}y_{uw}$, $Q(I(y_{vu}),I(y_{vw}))$ and $Q(I(y_{vw}),I(y_{vu}))$
by $y_{uvw}-y_{vu}y_{vw}$, $Q(I(y_{wu}),I(y_{wv}))$ and
$Q(I(y_{wv}),I(y_{wu}))$ by $y_{uvw}-y_{wu}y_{wv}$.

More formally, to compute $Q(y)$. Let $C(T)\in\mathbb{R}^{6\times 6}$ be
matrix that

$\displaystyle C(T)=diag(C^{(1)}(T),C^{(2)}(T),...,C^{(6)}(T))$

where

$\displaystyle C^{(1)}(T)=C^{(2)}(T)=COV_{u}(v,w)=y_{uvw}-y_{uv}y_{uw}$
$\displaystyle C^{(3)}(T)=C^{(4)}(T)=COV_{v}(u,w)=y_{uvw}-y_{vu}y_{vw}$
$\displaystyle C^{(5)}(T)=C^{(6)}(T)=COV_{w}(v,u)=y_{uvw}-y_{wv}y_{wu}$

Let $Head(T)\in\mathbb{R}^{6\times t}$ be a binary matrix, defined as
$Head(T)(i,I(a))=1$ when:

$\displaystyle(i,a)\in\\{(1,y_{uv}),(2,y_{uw}),(3,y_{vu}),(4,y_{vw}),(5,y_{wu}),(6,y_{wv})\\}$

and 0 otherwise. Similarly, we define $Tail(T)\in\mathbb{R}^{6\times t}$ as a
binary matrix, defined as $Tail(T)(i,I(a))=1$ when:

$\displaystyle(i,a)\in\\{(1,y_{uw}),(2,y_{uv}),(3,y_{vw}),(4,y_{vu}),(5,y_{wv}),(6,y_{wu})\\}$

We can then express $Q(y)$ as:

$\displaystyle
Q(y)=\sum_{T\in\mathcal{T}}\eta_{T}(y)\cdot\left(Head^{\intercal}(T)\cdot
C(T)\cdot Tail(T)\right)$

Let
$\mathcal{T}(I_{i},I_{j},I_{k})=\\{(y_{uv},y_{uw},y_{vw},y_{uvw})\in\mathcal{T}\mid
y_{uv}\leq y_{uw}\leq y_{vw},y_{uv}\in I_{i},y_{vw}\in I_{j},y_{uv}\in
I_{k}\\}$ be the set of triangles within the intervals $I_{i},I_{j},I_{k}$.
For any two triangles $T$ with $(y_{uv}=a,y_{uw}=b,y_{vw}=c)$ and $T^{\prime}$
with $(y_{uv}=a^{\prime},y_{uw}=b^{\prime},y_{vw}=c^{\prime})$, if $T$ and
$T^{\prime}$ are located within the same interval, meaning
$I(a)=I(a^{\prime})$, $I(b)=I(b^{\prime})$, and $I(c)=I(c^{\prime})$, then we
have $Head(T)=Head(T^{\prime})$ and $Tail(T)=Tail(T^{\prime})$. Given
$I_{i},I_{j},I_{k}$, define $Head(I_{i},I_{j},I_{k})=Head(T)$ (or
$Tail(I_{i},I_{j},I_{k})=Tail(T)$), where $T$ is an arbitrary triangle such
that $T\in\mathcal{T}(I_{i},I_{j},I_{k})$. We can then express $Q(y)$ as:

$\displaystyle
Q(y)=\sum_{I_{i},I_{j},I_{k}}Head^{\intercal}(I_{i},I_{j},I_{k})\cdot\left(\sum_{T\in\mathcal{T}(I_{i},I_{j},I_{k})}\eta_{T}(y)\cdot
C(T)\right)\cdot Tail(I_{i},I_{j},I_{k})$

Since $Q(y)\succeq 0$, it provides a constraint for $\eta_{T}(y)$. Our target
is to show that $\sum_{T}\eta_{T}(y)\cdot(\Delta(T)-\mathrm{cost}(T))\geq 0$
under the constraint that $Q(y)\succeq 0$. We will consider all possible
triangles in each range $\mathcal{T}(I_{i},I_{j},I_{k})$ and there will be at
most $O(t^{3})$ different range. For any solution $y$, the triangle
$T=\\{(y_{uv},y_{uw},y_{vw},y_{uvw})\mid y_{uv}\leq y_{uw}\leq y_{vw}\\}$
satisfies the triangle inequality, that is $1-y_{uw}+1-y_{vw}\geq 1-y_{uv}$.
Therefore, given range $I_{i},I_{j},I_{k}$, we assume that $l(I_{i})\geq
l(I_{j})+l(I_{k})-1$, $r(I_{j})\leq 1+l(I_{i})-l(I_{k})$ and $r(I_{k})\leq
1+l(I_{i})-l(I_{j})$, since there won’t be any triangles in the range when the
above inequality doesn’t hold. If necessary, we can truncate intervals to
ensure that these inequalities hold true.

In each range $I_{i},I_{j},I_{k}$, we will use
$\tilde{d}(I_{i},I_{j},I_{k})=min_{T\in\mathcal{T}(I_{i},I_{j},I_{k})}(\Delta(T)-\mathrm{cost}(T))$
to establish a lower bound on $\Delta(T)-\mathrm{cost}(T)$.
$\tilde{d}(I_{i},I_{j},I_{k})$ can be precomputed and there will be at most
$O(t^{3})$ different $\tilde{d}$ value. We first show that
$\tilde{d}(I_{i},I_{j},I_{k})$ is a lower bound even for degenerate triangle.
Recall that we treat degenerate triangle as triangle with $y$ value
$(y_{uv},y_{uv},1,y_{uv})$.

######  Lemma 58.

Let $T=(u,v)$ be a degenerate triangle, for any budget function $b^{+},b^{-}$
such that $b^{+}(0)=0$, then

$\displaystyle cost(u,v)-\Delta(u,v)\geq\tilde{d}(I(y_{uv}),I(y_{uv}),I(1))$

###### Proof.

Let $T_{1}$ represent the $+\\!+\\!+$ triangle with
$(y_{uv},y_{uv},1,y_{uv})$.If $(u,v)$ is a positive edge and $y_{uv}\geq 2/3$,
then $cost(u,v)=0$ and $\Delta(u,v)=2b^{+}(x_{uv})$. In this case,
$cost(T_{1})=0$ and $\Delta(T_{1})=2b^{+}(x_{uv})+b^{+}(0)$. If $(u,v)$ is a
positive edge and $y_{uv}<2/3$, we have $cost(u,v)=2(1-y_{uv})$ and
$\Delta(u,v)=2b^{+}(x_{uv})$. For $T_{1}$ in this scenario,
$cost(T_{1})=2(1-y_{uv})$ and $\Delta(T_{1})=2b^{+}(x_{uv})+b^{+}(0)y_{uv}$.
In either case, we observe that
$\Delta(u,v)-cost(u,v)=\Delta(T_{1})-cost(T_{1})\geq\tilde{d}(I(y_{uv}),I(y_{uv}),I(1))$.

Let $T_{2}$ be the $-\\!-\\!+$ triangle with $(y_{uv},y_{uv},1,y_{uv})$. If
$(u,v)$ is a negative edge, then $cost(u,v)=2y_{uv}$ and
$\Delta(u,v)=2b^{-}(x_{uv})$. For $T_{2}$, we have
$cost(T_{2})=2y_{uv}+2y_{uv}-2y_{uv}^{2}$ and
$\Delta(T_{2})=2b^{-}(x_{uv})+b^{+}(0)(2y_{uv}-y_{uv}^{2})$. Therefore, we
conclude that
$\Delta(u,v)-cost(u,v)\geq\Delta(T_{2})-cost(T_{2})\geq\tilde{d}(I(y_{uv}),I(y_{uv}),I(1))$.

∎

We still need to represent $Q$ using $\eta_{T}$. The problem is there might be
infinite types of triangles in each range $\mathcal{T}(I_{i},I_{j},I_{k})$,
and we are not able to list every possible triangle. To solve this problem,
our last observation is that, for $i\in[1,6]$, $C^{(i)}(T)$ is a multi-linear
function in terms of $y_{uv},y_{uw},y_{vw}$ and $y_{uvw}$.

Since $C^{(i)}(T)$ is multi-linear, we only need to consider 16 different
triangles in each range to cover all possible triangles, where those
triangles’ $y$ value are

$\displaystyle y_{uv}$
$\displaystyle\in\\{l(I_{i}),r(I_{i})\\},y_{uw}\in\\{l(I_{j}),r(I_{j})\\},y_{vw}\in\\{l(I_{k}),r(I_{k})\\}$
$\displaystyle y_{uvw}$
$\displaystyle\in\\{max(0,(l(I_{i})+l(I_{j})+l(I_{k})-1)/2),r(I_{k})\\}.$

The $y_{uvw}$ constraints comes from the fact that $y_{uvw}\leq y_{vw}$ and
$y_{uw}+y_{uv}+y_{vw}-2y_{uvw}\leq 1$. Each triangle might be considered in
different ranges multiple times and we shall treat them as different types of
triangles. Let $\mathcal{T_{D}}(I_{i},I_{j},I_{k})$ be the set of triangles
containing this 16 triangles in $\mathcal{T}(I_{i},I_{j},I_{k})$ and
$\mathcal{T_{D}}=\cup_{I_{i},I_{j},I_{k}}\mathcal{T_{D}}(I_{i},I_{j},I_{k})$,
we can set up a semi-definite programming to lower bound
$\sum_{T}\eta_{T}(y)\cdot(\Delta(T)-\mathrm{cost}(T))$. In factor-revealing
SDP, the variables are $\eta_{T}$ that represent the ratio of triangles
$T\in\mathcal{T_{D}}$ and $N\cdot\eta_{T}$ is the number of triangle of $T$,
where $N=\frac{n(n-1)(n-2)}{6}+\frac{n(n-1)}{2}=\frac{n(n-1)(n+1)}{6}$.
$\tilde{d}(I_{i},I_{j},I_{k})$, $Head^{\intercal}(I_{i},I_{j},I_{k})$, $C(T)$
and $Tail(I_{i},I_{j},I_{k})$ are constant and can be pre-computed.

$\min\qquad\sum_{I_{i},I_{j},I_{k}}\sum_{T\in\mathcal{T_{D}}(I_{i},I_{j},I_{k})}\eta_{T}\cdot\tilde{d}(I_{i},I_{j},I_{k})\qquad\text{s.t.}$
(factor-revealing SDP) $\displaystyle
Q=\sum_{I_{i},I_{j},I_{k}}Head^{\intercal}(I_{i},I_{j},I_{k})\left(\sum_{T\in\mathcal{T_{D}}(I_{i},I_{j},I_{k})}\eta_{T}\cdot
C(T)\right)\cdot Tail(I_{i},I_{j},I_{k})\succeq 0$ $\displaystyle\eta_{T}\geq
0\qquad\qquad\qquad\qquad\qquad\qquad\forall T\in\mathcal{T_{D}}$
$\displaystyle\sum_{T\in\mathcal{T_{D}}}\eta_{T}=1,\qquad\qquad\qquad\qquad\qquad\qquad\qquad$

Our main theorem regarding the SDP program is that

######  Theorem 59.

For any cluster LP solution $z_{S}$ and $y$ , let
${\mathrm{OPT}_{\mathrm{SDP}}}$ be the optimal solution for factor-revealing
SDP, then

$\displaystyle\sum_{T}\eta_{T}(y)\cdot(\Delta(T)-\mathrm{cost}(T))\geq
N\cdot{\mathrm{OPT}_{\mathrm{SDP}}}$

where $N=\frac{n(n-1)(n+1)}{6}$ is the number of degenerate and non-degenerate
triangles.

###### Proof.

Note that $\tilde{d}(I_{i},I_{j},I_{k})$ is the lower bound of
$\Delta(T)-\mathrm{cost}(T)$ for any $T\in\mathcal{T}(I_{i},I_{j},I_{k})$.
Hence, we have:

$\displaystyle\sum_{T}\eta_{T}(y)\cdot(\Delta(T)-\mathrm{cost}(T))\geq\sum_{I_{i},I_{j},I_{k}}\sum_{T\in\mathcal{T}(I_{i},I_{j},I_{k})}\eta_{T}(y)\cdot\tilde{d}(I_{i},I_{j},I_{k})$

The difficulty of the proof arises from the fact that we only consider
triangles from $\mathcal{T_{D}}(I_{i},I_{j},I_{k})$, which contains only 16
triangles. We will show that we can use triangles from $\mathcal{T_{D}}$ to
represent $Q$ and the objective value is at most
$\sum_{I_{i},I_{j},I_{k}}\sum_{T\in\mathcal{T}(I_{i},I_{j},I_{k})}\eta_{T}(y)\cdot\tilde{d}(I_{i},I_{j},I_{k})$.
For any triangle $T$ with $(y_{uv}\in I_{i},y_{uw}\in I_{j},y_{vw}\in I_{k})$
and $l(I_{i})\leq l(I_{j})\leq l(I_{k})$, let $T_{1},T_{2},...,T_{16}$ be the
16 triangles from $\mathcal{T_{D}}(I_{i},I_{j},I_{k})$. We will later show
that there exist $\lambda_{i}\geq 0$ such that
$C(T)=\sum_{i\in[1,16]}\lambda_{i}\cdot C(T_{i})$ and
$\sum_{i\in[1,16]}\lambda_{i}=1$. Therefore, we can use
$T_{1},T_{2},...,T_{16}$ to replace $T$ without affecting the $Q$ value. As we
use $\tilde{d}(I_{i},I_{j},I_{k})$ in the objective function and
$\sum_{i\in[1,16]}\lambda_{i}=1$, this substitution doesn’t impact the
objective value either.

Combining these findings, for any solution $y$ in cluster LP, we can deduce
the existence of a feasible solution $\eta_{T}$ from factor-revealing SDP such
that $\sum\eta_{t}=1$ and $N\cdot Q(\eta_{T})=Q(y)$. Therefore, we have

$\displaystyle\sum_{T}\eta_{T}(y)\cdot(\Delta(T)-\mathrm{cost}(T))$
$\displaystyle\geq\sum_{I_{i},I_{j},I_{k}}\sum_{T\in\mathcal{T}(I_{i},I_{j},I_{k})}\eta_{T}(y)\cdot\tilde{d}(I_{i},I_{j},I_{k})$
$\displaystyle\geq\sum_{I_{i},I_{j},I_{k}}\sum_{T\in\mathcal{T_{D}}(I_{i},I_{j},I_{k})}N\cdot\eta_{T}\cdot\tilde{d}(I_{i},I_{j},I_{k})\geq
N\cdot{\mathrm{OPT}_{\mathrm{SDP}}}$

We still need to demonstrate the existence of $\lambda_{i}\geq 0$ such that
$C(T)=\sum_{i\in[1,16]}\lambda_{i}\cdot C(T_{i})$ and
$\sum_{i\in[1,16]}\lambda_{i}=1$. For any triangle
$T=(y_{uv},y_{uw},y_{vw},y_{uvw})$, consider triangle
$T_{1}=(l(I_{i}),y_{uw},y_{vw},y_{uvw})$ and
$T_{2}=(r(I_{i}),y_{uw},y_{vw},y_{uvw})$ with
$\lambda=\frac{y_{uv}-l(I_{i})}{r(I_{i})-l(I_{i})}$. We then have
$C^{(i)}(T)=(1-\lambda)C^{(i)}(T_{1})+\lambda C^{(i)}(T_{2})$ for $i\in[1,6]$.
We can apply the same transformation to $y_{uw},y_{vw},y_{uvw}$ since
$C^{(i)}(T)$ is multilinear. This completes the proof. ∎

Theorem 59 provides a valuable method for establishing a lower bound on
$\sum_{T}\eta_{T}(y)\cdot(\Delta(T)-\mathrm{cost}(T))$ for any given solution
and budget function. To proceed with the computation of this lower bound, we
need to solve factor-revealing SDP. It’s important to emphasize that solving
factor-revealing SDP is completely independent of cluster LP. The value of
${\mathrm{OPT}_{\mathrm{SDP}}}$ is determined solely by the chosen budget
function and the selected intervals $I_{1},I_{2},...,I_{t}$.

The estimation errors, which is the difference between
$\sum_{T}\eta_{T}(y)\cdot(\Delta(T)-\mathrm{cost}(T))$ and
${\mathrm{OPT}_{\mathrm{SDP}}}$, mainly arise from two sources. First, we use
$\tilde{d}(I_{i},I_{j},I_{k})$ as an estimated value for all triangles within
$T_{D}(I_{i},I_{j},I_{k})$. Second, some of the triangles we consider may
violate the triangle inequality, and there’s the possibility that $y_{uvw}$
could violate its constraint as defined in cluster LP.

Given the budget function, the accuracy of our estimation improves with a
greater number of chosen intervals, but this also leads to longer computation
times for solving ${\mathrm{OPT}_{\mathrm{SDP}}}$. Additionally, to enhance
the accuracy of computing ${\mathrm{OPT}_{\mathrm{SDP}}}$, we employ two key
techniques. Firstly, we introduce an additional SDP constraint, and secondly,
we discretize the values of $y_{uvw}$.

#### Frequency Constraint.

We can set up another constraint for $\eta_{T}$. Similarly, given a node $u$,
consider the frequency matrix

$\displaystyle F_{u}(I_{j},I_{k})=|\\{v\in V,w\in V\mid y_{uv}\in
I_{j},y_{uw}\in I_{k}\\}|=\sum_{y_{uv}\in I_{j},y_{uw}\in I_{k}}1$

$F_{u}(I_{j},I_{k})$ is the number of pairs such that $y_{uv}\in I_{j}$ and
$y_{uw}\in I_{k}$. We want to mention $v$ and $w$ might be $u$. Let
$freq\in\mathbb{R}^{t}$ such that $freq(I_{j})=|\\{v\in V\mid y_{uv}\in
I_{j}\\}|$, then we can represent $F_{u}$ as

$\displaystyle F_{u}=freq^{\intercal}\cdot freq$

which implies $F_{u}$ is PSD, too. We will follow the discretization strategy
of $Q$ matrix. Let $F=\sum_{u}F_{u}$ and $A\in\mathbb{R}^{6\times 6}$ is
defined as

$\displaystyle A=diag(1,1,1,1,1,1)$

Then the increase of $F$ causing by $T$ is

$\displaystyle Head^{\intercal}(T)\cdot A\cdot Tail(T)$

It’s worth noting this increase holds even for degenerate triangles. For any
degenerate triangle $(u,v)$, it raises $F(I(y_{uv}),I(y_{uv}))$,
$F(I(y_{uv}),I(1))$, and $F(I(1),I(y_{uv}))$ by 2, echoing the increase seen
in the triangle with the $y$ value $(y_{uv},y_{uv},1,y_{uv})$. However, unlike
the $Q_{u}$ vector, $F_{u}$ also considers cases where $v=u$ and $w=u$. In the
$Q_{u}$ vector, this case doesn’t impact $Q_{u}$ due to
$y_{uuu}-y_{uu}y_{uu}=0$. We need to increment $F(I(1),I(1))$ by $n$ since
$\eta(y)$ does not account for $v=u$ and $w=u$. Fortunately, we already
include the $+\\!+\\!+$ triangle $T_{3}=(1,1,1,1)$; given that $T_{3}$ doesn’t
influence the matrix $Q$ value and $\Delta(T_{3})-cost(T_{3})=0$, each
occurrence of $T_{3}$ raises $F(I(1),I(1))$ by 6. By increasing
$\eta_{T_{3}}(y)$ by $n/6$, we can effectively represent $F$ as:

$\displaystyle
F(y)=\sum_{I_{i},I_{j},I_{k}}Head^{\intercal}(I_{i},I_{j},I_{k})\left(\sum_{T\in\mathcal{T}(I_{i},I_{j},I_{k})}\eta_{T}(y)\cdot
A\right)\cdot Tail(I_{i},I_{j},I_{k})$

Given that $A$ is a constant matrix, any $T$ can be utilized to encompass all
triangles from $\mathcal{T}(I_{i},I_{j},I_{k})$ for $F$.

#### Discretization for $y_{uvw}$.

Another technique that enhances estimation accuracy involves discretizing the
$y_{uvw}$ values. We achieve this by subdividing the interval
$[max(0,(l(I_{i})+l(I_{j})+l(I_{k})-1)/2),r(I_{k})]$ into numerous sub-
intervals. The specific manner in which we partition this interval depends on
both the interval’s length and its significance in the overall estimation.

However, it’s crucial to note that discretizing $y_{uvw}$ results in a
substantial increase in the number of triangles to be considered. This surge
may render the final SDP impractical to solve. The formulation of our ultimate
factor-revealing SDP is provided below:

$\min\qquad\sum_{I_{i},I_{j},I_{k},I_{l}}\sum_{T\in\mathcal{T_{D}}(I_{i},I_{j},I_{k},I_{l})}\eta_{T}\cdot\tilde{d}(I_{i},I_{j},I_{k},I_{l})\qquad\text{s.t.}$
(factor-revealing SDP) $\displaystyle
Q=\sum_{I_{i},I_{j},I_{k}}Head^{\intercal}(I_{i},I_{j},I_{k})\left(\sum_{I_{l},T\in\mathcal{T_{D}}(I_{i},I_{j},I_{k},I_{l})}\eta_{T}\cdot
C(T)\right)\cdot Tail(I_{i},I_{j},I_{k})\succeq 0$ $\displaystyle
F=\sum_{I_{i},I_{j},I_{k}}Head^{\intercal}(I_{i},I_{j},I_{k})\left(\sum_{I_{l},T\in\mathcal{T_{D}}(I_{i},I_{j},I_{k},I_{l})}\eta_{T}\cdot
A\right)\cdot Tail(I_{i},I_{j},I_{k})\succeq 0$ $\displaystyle\eta_{T}\geq
0\qquad\qquad\qquad\qquad\qquad\qquad\forall T\in\mathcal{T_{D}}$
$\displaystyle\sum_{T\in\mathcal{T_{D}}}\eta_{T}=1,\qquad\qquad\qquad\qquad\qquad\qquad$

where
$\tilde{d}(I_{i},I_{j},I_{k},I_{l})=min_{T\in\mathcal{T}(I_{i},I_{j},I_{k},I_{l})}(\Delta(T)-\mathrm{cost}(T))$,
and $\mathcal{T_{D}}(I_{i},I_{j},I_{k},I_{l})$ is the set of triangles such
that

$\displaystyle y_{uv}$
$\displaystyle\in\\{l(I_{i}),r(I_{i})\\},y_{uw}\in\\{l(I_{j}),r(I_{j})\\},y_{vw}\in\\{l(I_{k}),r(I_{k})\\},y_{uvw}\in\\{l(I_{l}),r(I_{l})\\}.$

By appropriately setting intervals, we can demonstrate that
${\mathrm{OPT}_{\mathrm{SDP}}}$ remains non-negative, as affirmed in Lemma 60,
even for a reduced budget function. The primary challenge lies in achieving a
balance between estimation error and the running time of solving factor-
revealing SDP in practice. For a more in-depth explanation of the specific
settings of Lemma 60, please refer to the details provided in Appendix B.

######  Lemma 60.

For budget functions $b^{+}\equiv b^{+}_{1.437}$ and $b^{-}\equiv
b^{-}_{1.437}$ Let ${\mathrm{OPT}_{\mathrm{SDP}}}$ be the optiamal value for
factor-revealing SDP, there exist intervals $I_{1},I_{2},...,I_{t}$ and
intervals for $y_{uvw}$ such that ${\mathrm{OPT}_{\mathrm{SDP}}}=0$.

###### Proof of Lemma 11.

For budget functions $b^{+}\equiv b^{+}_{1.437}$ and $b^{-}\equiv
b^{-}_{1.437}$, For degenerate and non-degenerate triangles, based on Theorem
59 and Lemma 60, we know that

$\displaystyle\sum_{T}\eta_{T}(y)\cdot(\Delta(T)-\mathrm{cost}(T))\geq
N\cdot{\mathrm{OPT}_{\mathrm{SDP}}}=0.$

∎

##  8 1.33-gap for Cluster LP

In this section, we show that the cluster LP has a gap of $4/3$, proving
Theorem 4 restated below.

See 4

The graph of the plus edges of our gap instance is based on the line graph of
a base graph; given a based graph $H=(V_{H},E_{H})$, our correlation
clustering instance is $G=(V_{G},E_{G})$ where $V_{G}=E_{H}$ and $e,f\in
V_{G}$ have a plus edge in $G$ if they share a vertex in $V_{H}$.

A high-level intuition is the following: LPs cannot distinguish between a
random graph and a nearly bipartite graph. Consider vertices of $H$ as ideal
clusters in $G$ containing their incident edges. Given a random graph $H$, the
LP fractionally will think that it is nearly bipartite, implying that the
almost entire $E_{H}$ can be partitioned into $n/2$ ideal clusters. Of course,
integrally, such a partition is not possible in random graphs. For the cluster
LP, it suffices to consider a complete graph instead of a random graph. We
believe (but do not prove) that such a gap instance can be extended to
stronger LPs (e.g., Sherali-Adams strengthening of the cluster LP), because it
is known that Sherali-Adams cannot distinguish a random graph and a nearly
bipartite graph [CMM09].

###### Proof of Theorem 4.

Let $H=(V_{H},E_{H})$ be a complete graph on $n$ vertices. Let $d=n-1$ be the
degree of $H$. Our correlation clustering instance $G=(V_{G},E_{G})$ is the
line graph of $H$; $V_{G}=E_{H}$ and $e,f\in E_{H}$ has $+$ edge in $G$ if and
only if they share a vertex in $H$. The $+$ degree of each $e\in E_{H}$ in $G$
is $2d-2$.

Consider the following solution for the cluster LP: for every $v\in V_{H}$,
let $E_{v}\subseteq E_{H}$ be the $d$ edges containing $v$. The cluster LP has
$z_{E_{v}}=1/2$ for every $v\in v_{H}$. Each $e\in E_{H}$ belongs to two
fractional clusters, each of which has its $d-1$ plus neighbors, so
fractionally $d-1$ plus edges incident on it are violated. Since each violated
edge is counted twice, the LP value is $\binom{n}{2}(d-1)/2$.

Let us consider the integral optimal correlation clustering of $G$. Consider a
cluster $C$ in the clustering. Note that every vertex in $C$ has at least
$|C|/2$ plus neighbors in $C$, which implies $|C|\leq 4d$. We apply the
following procedure to $C$ to partition it further.

######  Claim 61.

There is a partition of $C$ into $C_{1},\dots,C_{r}$ such that (1) each
$C_{i}$ is a subset of $E_{v}$ for some $v\in V_{H}$, and (2) replacing $C$ by
$C_{1},\dots,C_{r}$ in the correlation clustering solution increases the
objective function by at most $35|C|$.

###### Proof.

For $v\in V_{H}$, let $n_{v}:=|C\cap E_{v}|$. Note that $\sum_{v}n_{v}=2|C|$.
Without loss of generality, assume $V_{H}=\\{v_{1},\dots,v_{n}\\}$ with
$n_{v_{1}}\geq\dots\geq n_{v_{n}}$. If $e=(v_{i},v_{j})\in C$ has $i,j>8$,
then the number of its plus neighbors in $C$ is
$n_{v_{i}}+n_{v_{j}}<2\cdot\frac{1}{8}\cdot 2|C|=|C|/2$, so it should not
exist in $C$. So, every edge is incident on $v_{i}$ for some $i\leq 8$.

Let us make at most $\binom{8}{2}=28$ edges in $C$ between $v_{1},\dots,v_{8}$
as singleton clusters; the objective function increases by at most $28|C|$.
Then partition the remaining $C$ into $E_{1},\dots,E_{8}$ where $E_{i}:=C\cap
E_{v_{i}}$. Each $e\in E_{i}$ has at most seven plus neighbors in $\cup_{j\neq
i}E_{j}$, so the objective function increases by at most $7|C|$. So, we
partitioned $C$ into $C_{1},\dots,C_{r}$ where all the edges in $C_{i}$ share
a common endpoint. We increased the objective function by at most $35|C|$. ∎

After we apply the above procedure to every cluster $C$, we increased the cost
by at most $35|V_{H}|\leq 35n^{2}$ and all the edges in a cluster $C$ share a
common endpoint. For $v\in V_{H}$, let $C_{v}$ be the cluster in the solution
whose common endpoint is $v$. (If there are many of them, merging them will
strictly improve the objective function value.) Without loss of generality,
there are $t$ such clusters $C_{v_{1}},\dots,C_{v_{t}}$ and let
$n_{i}:=|C_{v_{i}}|$ such that $n_{1}\geq\dots\geq n_{t}$.

######  Claim 62.

$\sum_{i=1}^{t}n_{i}^{2}\leq n^{3}/3.$

###### Proof.

The LHS is monotone in $(n_{1},\dots,n_{t})$, and if there is an edge
$(v_{i},v_{j})\in C_{j}$ with $j>i$ (which implies $n_{i}\geq n_{j}$), the LHS
strictly improves by moving $(v_{i},v_{j})$ to $C_{i}$. Therefore, the
configuration that maximizes the LHS is when $t=n$ and $C_{v_{i}}$ contains
all the edges of $H$ not incident on $v_{1},\dots,v_{i-1}$. In that case, the
LHS is

$\sum_{i=1}^{n-1}(n-i)^{2}=n^{3}\sum_{i=1}^{n-1}(\frac{n-i}{n})^{2}\cdot\frac{1}{n}\leq
n^{3}\int_{0}^{1}(1-x)^{2}dx=n^{3}[x-x^{2}+x^{3}/3]^{1}_{0}=n^{3}/3,$

as desired. ∎

Using this, we can prove a lower bound on the cost of our near-optimal
clustering. Note that every cluster is a clique of $+$edges. Thus, the only
edges violated are $+$edges. Moreover, there are at most
$\sum_{i\in[t]}n_{i}^{2}/2\leq n^{3}/6$ correctly clustered $+$edges. The cost
of our near-optimal clustering is the total number of $+$edges of $G$ minus
the number of correctly clustered $+$edges, namely at most
$\binom{n}{2}(d-1)-n^{3}/6=n^{3}/3-o(n^{3})$. Since the cost of the optimal
clustering is at most $35n^{2}$ lower than ours, it is still
$n^{3}/3-o(n^{3})$. The fractional solution has the value at most $n^{3}/4$,
so the gap is at least $4/3-o(1)$. ∎

##  9 1.04-NP Hardness

In this section, we show that it is NP-hard (under randomized reductions) to
obtain an algorithm with an approximation ratio of 24/23$\ \geq 1.043$,
proving Theorem 5 restated below.

The idea is similar to the gap for the cluster LP in Section 8, which is based
on the fact that the LPs generally cannot distinguish nearly bipartite graphs
and random graphs. The main difference, which results in a worse factor here,
is that other polynomial-time algorithms (e.g., SDPs) can distinguish between
them! So, we are forced to work with slightly more involved structures.

Still, we use a similar construction for $3$-uniform hypergraphs; let
$H=(V_{H},E_{H})$ be the underlying $3$-uniform hypergraph and
$G=(V_{G},E_{G})$ be the plus graph of the final Correlation Clustering
instance where $V_{G}=E_{H}$ and $e,f\in E_{H}$ has an edge in $G$ if they
share a vertex in $H$. We use the following hardness result of Cohen-Addad,
Karthik, and Lee [CAL22] that shows that it is hard to distinguish whether $H$
is nearly bipartite or close to a random hypergraph.

######  Theorem 63.

For any $\varepsilon>0$, there exists a randomized polynomial-time algorithm
that receives a 3-CNF formula $\phi$ as input and outputs a simple $3$-uniform
hypergraph $H=(V_{H},E_{H})$ where the degree of each vertex is $(1\pm o(1))d$
for some $d=\omega(|V_{H}|)$ such that the following properties are satisfied
with high probability.

  * •

(YES) If $\phi$ is satisfiable, there exists $U\subseteq V_{H}$ with
$|U|=|V_{H}|/2$ that intersects every hyperedge in $E_{H}$. Moreover, for
every $u\in U$, $|\\{e\in E_{H}:e\cap U=\\{u\\}\\}|\geq(1/2-\varepsilon)d$.

  * •

(NO) If $\phi$ is unsatisfiable, any set of $\gamma|V_{H}|$ vertices
($\gamma\in[0,1]$) do not intersect at least a $(1-\gamma)^{3}-\varepsilon$
fraction of hyperedges in $E_{H}$.

###### Proof.

The same reduction in Theorem 4.1 of (the arXiv version of) [CAL22] yields the
desired hardness. In the following, we highlight the difference between the
statement of Theorem 4.1 of [CAL22] and our Theorem 63 and briefly explain how
our additional properties are satisfied by their reduction.

  1. 1.

Regularity of $H$: Section 4.5 of [CAL22], based on an earlier weighted hard
instance, constructs the final hard instance $H=(V_{H},E_{H})$ as a certain
random hypergraph where the degree of each vertex $v$ is the sum of
independent $\\{0,1\\}$ variables with the same expected value. This expected
value is $\Theta(|V_{H}|^{1.5})$, so the standard Chernoff and union bound
argument will show that the degree of each vertex is almost the same with high
probability.

  2. 2.

In the (YES) case, for every $u\in U$, $|\\{e\in E_{H}:e\cap
U=\\{u\\}\\}|\geq(1/2-\varepsilon)d$: It follows from their construction in
Section 4.1. The construction is analogous to Håstad’s celebrated result on
Max-3SAT [Hås01] where in the (YES) case, almost three quarters of the clauses
have one true literal and almost one quarter have three true literals, so that
for each true literal $\ell$, roughly half of the clauses containing $\ell$
has it as the only true literal.

  3. 3.

In the (NO) case: the guarantee holds for any value of $\gamma\in[0,1]$
instead of just $0.5$: One can simply change $1/2$ to $1-\gamma$ in the proof
of Lemma 4.4 in Section 4.3. It is analogous to the fact that all nontrivial
Fourier coefficients vanish in Håstad’s result on Max-3SAT and Max-3LIN
[Hås01].

∎

Given such $H=(V_{H},E_{H})$, let $n:=|V_{H}|$. Our correlation clustering
instance $G=(V_{G},E_{G})$ is the line graph of $H$; $V_{G}=E_{H}$ and $e,f\in
E_{H}$ have a plus edge in $G$ if they share a vertex in $H$. This means that
every $e\in V_{G}$ has $(3\pm o(1))d$ plus edges incident on it; we used the
fact that $d=\omega(n)$ and $e$ has at most $O(n)$ other hyperedges that
intersect with $e$ with at least two points (which causes double counting).

#### YES case.

Consider $U\subseteq V_{H}$ guaranteed in Theorem 63. Our (randomized)
clustering is the following: randomly permute vertices to obtain
$U=\\{v_{1},\dots,v_{n/2}\\}$, and let $E_{i}:=\\{e\in E_{H}:v_{i}\in e\mbox{
and }e\cap\\{v_{1},\dots,v_{i-1}\\}=\emptyset\\}$. Since $U$ intersects every
$e\in E_{H}$, $(E_{1},\dots,E_{n/2})$ forms a partition of $E_{H}$.

We analyze the expected cost of this clustering. For each $e\in E_{H}$, let
$save(e)$ be (the number of plus neighbors in the same cluster) minus (the
number of minus neighbors in the same cluster). Intuitively, it is the amount
of saved cost between $e$ and its neighbors, compared to the situation where
$e$ is a singleton cluster. Then, the cost of our clustering is the total
number of plus edges of $G$, namely $|E_{H}|\cdot\frac{3(1\pm
o(1))d}{2}=nd^{2}\cdot\frac{(1\pm o(1))}{2}$, minus $\sum_{e\in
E_{H}}save(e)/2$.

Fix $v\in U$ and let $E_{v}:=\\{e\in E_{H}:v\in e\\}$,
$E^{\prime}_{v}:=\\{e\in E_{H}:e\cap U=\\{v\\}\\}$,
$E^{\prime\prime}_{v}:=E_{v}\setminus E^{\prime}_{v}$. Then $|E_{v}|=(1\pm
o(1))d$ and $|E^{\prime}_{v}|\geq(1/2-\varepsilon)d$. We would like to compute
$\operatorname*{{\mathbb{E}}}[|E_{i}|^{2}]$ over random permutations where $i$
is defined such that $v_{i}=v$. It is clear that $E^{\prime}_{v}\subseteq
E_{i}$. For each $e\in E^{\prime\prime}_{v}$, the probability that $e\in
E_{i}$ is at least $1/3$ (when $v$ comes before the other two vertices of $e$
in the random permutation). And two hyperedges $e,f\in E^{\prime\prime}_{v}$,
the probability that both are in $E_{i}$ is at least $1/5$ (when $v$ comes
first among $|e\cup f|\leq 5$ vertices). Therefore,

$\operatorname*{{\mathbb{E}}}[|E_{i}|^{2}]\geq|E^{\prime}_{i}|^{2}+2|E^{\prime}_{i}||E^{\prime\prime}_{i}|/3+|E^{\prime\prime}_{i}|^{2}/5\geq
d^{2}(1/4+1/6+1/20-O(\varepsilon))=d^{2}(7/15-O(\varepsilon)).$

Therefore, the total saving is at least $nd^{2}(7/30-O(\varepsilon))$ and the
final cost is at most
$nd^{2}(1/2-7/60+O(\varepsilon))=nd^{2}(23/60+O(\varepsilon))$.

#### NO case.

Our analysis will be similar to that of the gap instance, slightly more
complicated by the fact that we are working with a non-complete hypergraph.
Consider the optimal correlation clustering and consider one cluster $C$. For
$e\in C$, it has at most $(3\pm o(1))d$ plus edges in $G$, so
$|C|\leq(6+o(1))d$; otherwise, it is better to make $e$ a singleton cluster.
We prove that if $C$ is large, then we can partition $C$ into smaller clusters
where each cluster consists of hyperedges sharing the same vertex in $H$. For
$v\in E_{H}$, let $E_{v}\subseteq E_{H}$ be the set of hyperedges containing
$v$.

######  Claim 64.

There is a partition of $C$ into $C_{1},\dots,C_{r}$ such that (1) each
$C_{i}$ is a subset of $E_{v}$ for some $v\in V_{H}$, and (2) replacing $C$ by
$C_{1},\dots,C_{r}$ in the correlation clustering solution increases the
objective function by at most $O(n|C|)$.

###### Proof.

Without loss of generality, assume $V_{H}=\\{v_{1},\dots,v_{n}\\}$ and define
$n_{i}:=|C\cap E_{v_{i}}|$ such that $n_{1}\geq\dots\geq n_{n}$. Note that
$\sum_{i}n_{i}=3|C|$.

If $e=(v_{i},v_{j},v_{k})$ with $i,j,k>20$, then
$n_{i}+n_{j}+n_{k}<3\cdot(3|C|/20)<|C|/2$, which implies that $e$ has more
minus neighbors than plus neighbors in $C$, leading to contradiction. So,
every hyperedge is incident on $v_{i}$ for some $i\leq 20$.

Since two vertices of $H$ have at most $n$ hyperedges containing both of them,
let us make at most $n\cdot\binom{10}{2}$ hyperedges in $C$ that contain at
least two of $v_{1},\dots,v_{20}$ as singleton clusters; the objective
function increases by at most $n\cdot\binom{10}{2}\cdot|C|$. Then partition
the remaining $C$ into $E_{1},\dots,E_{20}$ where $E_{i}:=C\cap E_{v_{i}}$.
Each $e\in E_{i}$ has at most $2\cdot 20\cdot n$ plus edges in $\cup_{j\neq
i}E_{j}$ ($20$ choices for $v_{j}$, $2$ choices for a vertex in
$e\ni\\{v_{i}\\}$, and $n$ choices for hyperedges containing both vertices),
so the objective function increases by at most $O(n|C|)$. So, we partitioned
$C$ into $C_{1},\dots,C_{r}$ where all the hyperedges in $C_{i}$ share a
common endpoint. In total, we increased the objective function by at most
$O(n|C|)$. ∎

Applying the above procedure for every cluster $C$ increases the objective
function by at most $O(n\cdot|E_{H}|)=O(n^{2}d)$. Then, we have a clustering
where all the edges in a cluster $C$ share a common endpoint. $C$ forms a
clique in $H$. For $v\in V_{H}$, let $C_{v}$ be the cluster in the solution
whose common endpoint is $v$. (If there are many of them, merging them will
strictly improve the objective function value.) Without loss of generality,
there are $t$ such clusters $C_{v_{1}},\dots,C_{v_{t}}$ and let
$c_{i}:=|C_{v_{i}}|$ such that $c_{1}\geq\dots\geq c_{t}$.

######  Claim 65.

$\sum_{i=1}^{t}c_{i}^{2}\leq d^{2}n(0.2+O(\sqrt{\varepsilon}))$, where
$\varepsilon$ is the parameter from Theorem 63.

###### Proof.

Here, we use the NO case guarantee from Theorem 63: for any $\gamma\in[0,1]$
and choice of $\gamma n$ vertices, it covers at most
$1-(1-\gamma)^{3}+\varepsilon=3\gamma-3\gamma^{2}+\gamma^{3}+\varepsilon$
fraction of the edges, which is equivalent to: for every $i\in[n]$,

$\sum_{j=1}^{i}c_{i}\leq(3(i/n)-3(i/n)^{2}+(i/n)^{2}+\varepsilon)|E_{H}|.$
(71)

Let $\delta=o(1)$ be such that every vertex of $H$ has degree at most
$(1+\delta)d$, which means that $(1+\delta)d\geq c_{1}\geq\dots\geq c_{t}$.
And let $f_{i/n}:=c_{i}/((1+\delta)d)$. Then (71) becomes

$\frac{1}{n}\sum_{j=1}^{i}f_{j/n}\leq(3(i/n)-3(i/n)^{2}+(i/n)^{2}+\varepsilon)\frac{|E_{H}|}{(1+\delta)dn}\leq(3(i/n)-3(i/n)^{2}+(i/n)^{2}+\varepsilon)/3.$
(72)

(Note that $|E_{H}|\leq(1+\delta)dn/3$.) Interpreting
$\frac{1}{n}\sum_{j=1}^{i}f_{j/n}$ as $\int_{0}^{1}f(x)dx$ where
$f(x)=c_{\lceil xn\rceil}$, we have that
$\sum_{i=1}^{t}|c_{i}|^{2}\leq(1+\delta)^{2}d^{2}n\max_{f}\int_{0}^{1}f(x)^{2}dx$,
where the maximum is taken over functions $f:[0,1]\to[0,1]$ with the
constraints that

  1. 1.

For all $y\in[0,1]$,

$\int_{x=0}^{y}f(x)dx\leq y-y^{2}+y^{3}/3+\varepsilon/3.$ (73)

(Compared to (72), we add more constraints for every $y\in[0,1]$, but it is
valid to do so since the step function $f(\cdot)$ defined above satisfies all
these constraints; if (73) is violated for some value $y\in(i/n,(i+1)/n)$ for
some integer $i$, (72) is violated at $(i+1)/n$ because $f(y)$ stays the same
in the interval while the upper bound increases strictly less than linearly.)

  2. 2.

$f$ decreasing with $f(0)\leq 1$.

Then one see that the optimal $f$ satisfies either $f(y)=1$ or
$\int_{x=0}^{y}f(x)=y-y^{2}+y^{3}+\varepsilon/3$ for every $y\in[0,1)$. If it
is not satisfied at some $y$, we can increase $f(y)$ while decreasing $f(z)$
for some $z>y$, which will still satisfy the constraints and increase
$\int_{0}^{1}f(x)^{2}dx$. Therefore, we can conclude that $f(y)=1$ for
$y\leq\tau$ and

$\int_{x=0}^{y}f(x)dx=y-y^{2}+y^{3}/3+\varepsilon/3\Rightarrow
f(y)=(y-y^{2}+y^{3}/3+\varepsilon/3)^{\prime}=1-2y+y^{2}$

for $y>\tau$, where $\tau=\Theta(\sqrt{\varepsilon})$ is the solution of
$\tau=\tau-\tau^{2}+\tau^{3}+\varepsilon/3$. Then, we can bound

$\int_{x=0}^{1}f(x)^{2}dx\leq
O(\sqrt{\varepsilon})+\int_{x=0}^{1}(1-2x+x^{2})^{2}dx\leq
0.2+O(\sqrt{\varepsilon}),$

which implies that $\sum_{i}c_{i}^{2}\leq d^{2}n(0.2+O(\sqrt{\varepsilon}))$.
∎

Using this, we can prove a lower bound on the cost of our near-optimal
clustering. Note that every cluster is a clique of $+$edges. Thus, the only
edges violated are $+$edges. Moreover, there are at most
$\sum_{i\in[t]}c_{i}^{2}/2\leq d^{2}n(0.1+O(\sqrt{\varepsilon})$ correctly
clustered $+$edges. The cost of our near-optimal clustering is the total
number of $+$edges of $G$ minus the number of correctly clustered $+$edges,
namely at least
$nd^{2}(1/2-0.1-O(\sqrt{\varepsilon}))=nd^{2}(0.4-O(\sqrt{\varepsilon}))$.
Since the cost of the optimal clustering is at most $O(n^{2}d)$ lower than
ours, it is still $nd^{2}(0.4-O(\sqrt{\varepsilon}))$ using $d=\omega(n)$.

Since the value in the YES case is at most $(23/60+O(\varepsilon))nd^{2}$, so
the gap is almost $\frac{24}{23}\geq 1.043$.

##  10 Open Problems

We highlight several problems left open by this work.

  * •

Our algorithm computes a $(1+\epsilon)$-approximate solution for Cluster LP in
$n^{\text{poly}(1/\epsilon)}$ time. An intriguing question is whether Cluster
LP can be solved in time $f(\epsilon)\cdot\text{poly}(n)$, for some function
$f$. (e.g., $O(2^{\text{poly}(1/\epsilon)}n^{100})$).

  * •

Our analysis of the rounding procedure, which achieves a $1.437$-approximate
ratio, currently requires computer assistance. One challenge is to determine
whether a similar approximate ratio can be achieved without computer
assistance. Additionally, although computer assistance enables us to impose
more constraints on $\eta_{T}$—thereby slightly reducing the approximate
ratio—it remains substantially above the theoretical lower bound. Exploring
the possibility of achieving an approximate ratio of $4/3+\epsilon$, or even
surpassing the $4/3$ approximate ratio, represents a critical area for future
research.

  * •

Recent findings by Cohen-Addad, Lolck, Pilipczuk, Thorup, Yan, and Zhang
[CALP+24] demonstrate that a 1.847-approximate ratio is achievable in
$\tilde{O}(m)$ time, where $m$ is the number of $+$edges. Can we show some
kind of tradeoff between the running time and the approximate ratio?

## References

  * [ACG+15] Kook Jin Ahn, Graham Cormode, Sudipto Guha, Andrew McGregor, and Anthony Wirth.  Correlation clustering in data streams.  In Proceedings of the 32nd International Conference on Machine Learning (ICML), pages 2237–2246, 2015.
  * [ACN08] Nir Ailon, Moses Charikar, and Alantha Newman.  Aggregating inconsistent information: Ranking and clustering.  Journal of the ACM, 55(5):1–27, 2008.
  * [AHK+09] Rakesh Agrawal, Alan Halverson, Krishnaram Kenthapadi, Nina Mishra, and Panayiotis Tsaparas.  Generating labels from clicks.  In Proceedings of the Second ACM International Conference on Web Search and Data Mining, pages 172–181, 2009.
  * [AN23] Sara Ahmadian and Maryam Negahbani.  Improved approximation for fair correlation clustering.  In International Conference on Artificial Intelligence and Statistics, pages 9499–9516. PMLR, 2023.
  * [ARS09] Arvind Arasu, Christopher Ré, and Dan Suciu.  Large-scale deduplication with constraints using dedupalog.  In Proceedings of the 25th IEEE International Conference on Data Engineering (ICDE), pages 952–963, 2009.
  * [AW22] Sepehr Assadi and Chen Wang.  Sublinear time and space algorithms for correlation clustering via sparse-dense decompositions.  In Proceedings of the 13th Conference on Innovations in Theoretical Computer Science (ITCS), volume 215 of LIPIcs, pages 10:1–10:20, 2022.
  * [BBC04] Nikhil Bansal, Avrim Blum, and Shuchi Chawla.  Correlation clustering.  Machine learning, 56(1):89–113, 2004.
  * [BCMT22] Soheil Behnezhad, Moses Charikar, Weiyun Ma, and Li-Yang Tan.  Almost 3-approximate correlation clustering in constant rounds.  In Proceedings of 63rd Annual IEEE Symposium on Foundations of Computer Science, (FOCS), pages 720–731, 2022.
  * [BCMT23] Soheil Behnezhad, Moses Charikar, Weiyun Ma, and Li-Yang Tan.  Single-pass streaming algorithms for correlation clustering.  In Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 819–849, 2023.
  * [BGU13] Francesco Bonchi, Aristides Gionis, and Antti Ukkonen.  Overlapping correlation clustering.  Knowledge and Information Systems, 35(1):1–32, 2013.
  * [BRS11] Boaz Barak, Prasad Raghavendra, and David Steurer.  Rounding semidefinite programming hierarchies via global correlation.  In Proceedings of 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 472–481, 2011.
  * [BS06] Nikhil Bansal and Maxim Sviridenko.  The Santa Claus problem.  In Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC), pages 31–40, 2006.
  * [CAL22] Vincent Cohen-Addad and Euiwoong Lee.  Johnson coverage hypothesis: Inapproximability of k-means and k-median in $l_{p}$-metrics.  In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1493–1530. SIAM, 2022.
  * [CALP+24] Vincent Cohen-Addad, David Rasmussen Lolck, Marcin Pilipczuk, Mikkel Thorup, Shuyi Yan, and Hanwen Zhang.  Combinatorial correlation clustering, 2024.
  * [CCMU21] Mélanie Cambus, Davin Choo, Havu Miikonen, and Jara Uitto.  Massively parallel correlation clustering in bounded arboricity graphs.  In 35th International Symposium on Distributed Computing (DISC), volume 209 of LIPIcs, pages 15:1–15:18, 2021.
  * [CDK14] Flavio Chierichetti, Nilesh Dalvi, and Ravi Kumar.  Correlation clustering in MapReduce.  In Proceedings of the 20th ACM International Conference on Knowledge Discovery and Data Mining (SIGKDD), pages 641–650, 2014.
  * [CGW05] Moses Charikar, Venkatesan Guruswami, and Anthony Wirth.  Clustering with qualitative information.  Journal of Computer and System Sciences, 71(3):360–383, 2005.
  * [CHS24] Nairen Cao, Shang-En Huang, and Hsin-Hao Su.  Breaking 3-factor approximation for correlation clustering in polylogarithmic rounds.  In Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms (SODA), 2024.
  * [CKK+06] Shuchi Chawla, Robert Krauthgamer, Ravi Kumar, Yuval Rabani, and D. Sivakumar.  On the hardness of approximating multicut and sparsest-cut.  Computational Complexity, 15(2):94–114, 2006.
  * [CKL+24] Mélanie Cambus, Fabian Kuhn, Etna Lindy, Shreyas Pai, and Jara Uitto.  A $(3+\varepsilon)$-Approximate Correlation Clustering Algorithm in Dynamic Streams.  In Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms (SODA), 2024.
  * [CKP08] Deepayan Chakrabarti, Ravi Kumar, and Kunal Punera.  A graph-theoretic approach to webpage segmentation.  In Proceedings of the 17th International conference on World Wide Web (WWW), pages 377–386, 2008.
  * [CLLN23] Vincent Cohen-Addad, Euiwoong Lee, Shi Li, and Alantha Newman.  Handling correlated rounding error via preclustering: A 1.73-approximation for correlation clustering.  In Proceedings of the 64rd Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2023.
  * [CLM+21] Vincent Cohen-Addad, Silvio Lattanzi, Slobodan Mitrovic, Ashkan Norouzi-Fard, Nikos Parotsidis, and Jakub Tarnawski.  Correlation clustering in constant many parallel rounds.  In Proceedings of the 38th International Conference on Machine Learning (ICML), pages 2069–2078, 2021.
  * [CLMP22] Vincent Cohen-Addad, Silvio Lattanzi, Andreas Maggiori, and Nikos Parotsidis.  Online and consistent correlation clustering.  In Proceedings of International Conference on Machine Learning (ICML), pages 4157–4179, 2022.
  * [CLN22] Vincent Cohen-Addad, Euiwoong Lee, and Alantha Newman.  Correlation clustering with Sherali-Adams.  In Proceedings of 63rd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 651–661, 2022.
  * [CM23] Sayak Chakrabarty and Konstantin Makarychev.  Single-pass pivot algorithm for correlation clustering. Keep it simple!  In Thirty-seventh Conference on Neural Information Processing Systems, 2023.
  * [CMM09] Moses Charikar, Konstantin Makarychev, and Yury Makarychev.  Integrality gaps for Sherali-Adams relaxations.  In Proceedings of the 41st Annual ACM Symposium on Theory of Computing (STOC), pages 283–292, 2009.
  * [CMSY15] Shuchi Chawla, Konstantin Makarychev, Tselil Schramm, and Grigory Yaroslavtsev.  Near optimal LP rounding algorithm for correlation clustering on complete and complete $k$-partite graphs.  In Proceedings of the 47th Annual ACM Symposium on Theory of Computing (STOC), pages 219–228, 2015.
  * [CSX12] Yudong Chen, Sujay Sanghavi, and Huan Xu.  Clustering sparse graphs.  In Advances in Neural Information Processing Systems (Neurips), pages 2204–2212, 2012.
  * [DEFI06] Erik D. Demaine, Dotan Emanuel, Amos Fiat, and Nicole Immorlica.  Correlation clustering in general weighted graphs.  Theoretical Computer Science, 361(2-3):172–187, 2006.
  * [DMN23] Sami Davies, Benjamin Moseley, and Heather Newman.  Fast combinatorial algorithms for min max correlation clustering.  arXiv preprint arXiv:2301.13079, 2023.
  * [FGMS06] Lisa Fleischer, Michel X. Goemans, Vahab S. Mirrokni, and Maxim Sviridenko.  Tight approximation algorithms for maximum general assignment problems.  In Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 611–620, 2006.
  * [GG06] Ioannis Giotis and Venkatesan Guruswami.  Correlation clustering with a fixed number of clusters.  Theory of Computing, 2:249–266, 2006.
  * [GS11] Venkatesan Guruswami and Ali Kemal Sinop.  Lasserre hierarchy, higher eigenvalues, and approximation schemes for graph partitioning and quadratic integer programming with PSD objectives.  In Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 482–491, 2011.
  * [Hås01] Johan Håstad.  Some optimal inapproximability results.  Journal of the ACM, 48(4):798–859, 2001.
  * [HIA23] Holger Heidrich, Jannik Irmai, and Bjoern Andres.  A 4-approximation algorithm for min max correlation clustering.  arXiv preprint arXiv:2310.09196, 2023.
  * [KCMNT08] Dmitri V. Kalashnikov, Zhaoqi Chen, Sharad Mehrotra, and Rabia Nuray-Turan.  Web people search via connection analysis.  IEEE Transactions on Knowledge and Data Engineering, 20(11):1550–1565, 2008.
  * [KS09] Marek Karpinski and Warren Schudy.  Linear time approximation schemes for the Gale-Berlekamp game and related minimization problems.  In Proceedings of the 41st Annual ACM Symposium on Theory of Computing (STOC), pages 313–322, 2009.
  * [LMV+21] Silvio Lattanzi, Benjamin Moseley, Sergei Vassilvitskii, Yuyan Wang, and Rudy Zhou.  Robust online correlation clustering.  In Advances in Neural Information Processing Systems (Neurips), pages 4688–4698, 2021.
  * [MSS10] Claire Mathieu, Ocan Sankur, and Warren Schudy.  Online correlation clustering.  In Proceedings of 27th International Symposium on Theoretical Aspects of Computer Science (STACS), pages 573–584, 2010.
  * [PPO+15] Xinghao Pan, Dimitris S. Papailiopoulos, Samet Oymak, Benjamin Recht, Kannan Ramchandran, and Michael I. Jordan.  Parallel correlation clustering on big graphs.  In Advances in Neural Information Processing Systems (Neurips), pages 82–90, 2015.
  * [RT12] Prasad Raghavendra and Ning Tan.  Approximating CSPs with global cardinality constraints using SDP hierarchies.  In Proceedings of the 23d Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 373–387, 2012.
  * [Swa04] Chaitanya Swamy.  Correlation clustering: Maximizing agreements via semidefinite programming.  In Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 526–527, 2004.
  * [Vel22] Nate Veldt.  Correlation clustering via strong triadic closure labeling: Fast approximation algorithms and practical lower bounds.  In International Conference on Machine Learning (ICML), pages 22060–22083, 2022.
  * [VGW18] Nate Veldt, David F. Gleich, and Anthony Wirth.  A correlation clustering framework for community detection.  In Proceedings of the 2018 ACM World Wide Web Conference (WWW), pages 439–448, 2018.

##  Appendix A Preclustering

The goal of this section is to prove Theorem 14, which is repeated below: See
14

For convenience, we assume every $u$ has a self-loop in $E^{+}$. Let
$N^{+}_{u}$ be the set of $+$neighbors of $u$; so we have $u\in N^{+}_{u}$.
Let $d^{+}_{u}=|N^{+}_{u}|$ be its $+$degree. Let ${\mathcal{C}}^{*}$ be the
optimum clustering, and ${\mathrm{opt}}=\mathrm{obj}({\mathcal{C}}^{*})$ be
its cost. We assume $\varepsilon>0$ is at most a small enough constant; we
define $\beta=0.1$ to be an absolute constant.

###  A.1 Constructing Atoms

In the first step of the algorithm for the proof of Theorem 14, we define the
set ${\mathcal{K}}$ of atoms. We use any known $O(1)$-approximation algorithm
for the Correlation Clustering problem to obtain a clustering; for example, we
can use the $3$-approximation combinatorial algorithm of [ACN08] to obtain a
clustering ${\mathcal{C}}$ with $\mathrm{obj}({\mathcal{C}})\leq
3\cdot{\mathrm{opt}}$.

Our ${\mathcal{K}}$ is obtained from ${\mathcal{C}}$ by marking some vertices
and creating singletons for them. We view ${\mathcal{K}}$ both as a clustering
and as the set of atoms. The algorithm is described in Algorithm 4.

Algorithm 4 Construction of ${\mathcal{K}}$

1:for every non-singleton $C\in{\mathcal{C}}$ do

2: for every $u\in C$ do: mark $u$ if $|N^{+}_{u}\triangle
C|>\frac{\beta}{2}\cdot|C|$

3: if at least $\frac{\beta|C|}{3}$ vertices in $C$ are marked then mark all
vertices in $C$

4:let ${\mathcal{K}}$ be the clustering obtained from ${\mathcal{C}}$ by
removing marked vertices and creating a singleton cluster for each of them

5:return ${\mathcal{K}}$

######  Lemma 66.

$\mathrm{obj}({\mathcal{K}})\leq O\left(1\right)\cdot{\mathrm{opt}}$, where we
view ${\mathcal{K}}$ as a clustering.

###### Proof.

If a cluster $C$ has less than $\frac{\beta|C|}{3}$ marked vertices before
Step 3, then the cost incurred by separating the marked vertices in $C$ is at
most $\frac{2}{\beta}=O(1)$ times the cost of edges incident to these vertices
in ${\mathcal{C}}$. On the other hand, if $C$ has at least
$\frac{\beta|C|}{3}$ marked vertices before Step 3, the cost of edges incident
to $C$ in ${\mathcal{C}}$ is at least
$\frac{\beta}{2}\cdot|C|\cdot\frac{\beta|C|}{3}\cdot\frac{1}{2}=\Omega(|C|^{2})$.
The cost incurred by breaking $C$ into singletons is at most $|C|\choose 2$.
As every edge is charged at most twice, the cost incurred by creating
singletons for all marked vertices is at most
$O(1)\cdot\mathrm{obj}({\mathcal{C}})$. So $\mathrm{obj}({\mathcal{K}})\leq
O(1)\cdot{\mathrm{opt}}$ as $\mathrm{obj}({\mathcal{C}})\leq
3\cdot{\mathrm{opt}}$. ∎

######  Lemma 67.

For every non-singleton $K\in{\mathcal{K}}$, and every $u\in K$, we have
$|N^{+}_{u}\triangle K|<\beta|K|$.

###### Proof.

Assume $K\subseteq C$ for some $C\in{\mathcal{C}}$. So the vertices in
$C\setminus K$ are marked, the vertices in $K$ are unmarked, and $|C\setminus
K|<\frac{\beta|C|}{3}$. For every $u\in K$, we have $|N^{+}_{u}\triangle
C|\leq\frac{\beta}{2}\cdot|C|$ because it is unmarked. Then
$|N^{+}_{u}\triangle
K|\leq\frac{\beta}{2}\cdot|C|+\frac{\beta|C|}{3}=\frac{5\beta}{6}\cdot|C|\leq\frac{5\beta}{6}\cdot\frac{|K|}{1-\beta/3}\leq\beta|K|$
for our choice of $\beta$. ∎

######  Lemma 68.

Consider the optimum clustering ${\mathcal{C}}^{*}$. Any atom
$K\in{\mathcal{K}}$ is completely inside a cluster in ${\mathcal{C}}^{*}$.

###### Proof.

The lemma holds trivially if $K$ is a singleton. Assume towards the
contradiction that $K$ is a non-singleton and not inside a cluster in
${\mathcal{C}}^{*}$. By Lemma 67, we have that $|N^{+}_{u}\triangle
K|<\beta|K|$ for every $u\in K$. In particular, this implies that $|K\setminus
N^{+}_{u}|<\beta|K|$ and $|N^{+}_{u}\setminus K|<\beta|K|$. We consider two
cases as in [CLLN23].

First, suppose no cluster in ${\mathcal{C}}^{*}$ contains at least
$\frac{2|K|}{3}$ vertices in $K$. We consider the operation of removing all
vertices in $K$ from their respective clusters in ${\mathcal{C}}^{*}$, and
creating a single cluster $K$. The saving in cost is at least
$\frac{1}{2}\cdot|K|\cdot(\frac{|K|}{3}-\beta|K|)-\frac{1}{2}\cdot|K|\cdot\beta|K|=(\frac{1}{6}-\beta)|K|^{2}>0$,
as $\beta=0.1$. This contradicts that ${\mathcal{C}}^{*}$ is optimum.

Then, consider the other case where there is some $C\in{\mathcal{C}}$ with
$|C\cap K|\geq\frac{2|K|}{3}$. Let $u$ be any vertex in $K\setminus C$; it
must exist as $K$ is not completely inside $C$. Then, we consider the
operation of moving $u$ from its cluster to $C$. The saving in cost is at
least $(\frac{2}{3}-2\beta)|K|-\frac{|K|}{3}=(\frac{1}{3}-2\beta)|K|>0$ as
$\beta=0.1$, contradicting that ${\mathcal{C}}^{*}$ is optimum. ∎

With Lemma 68, we now restrict ourselves to clusterings that do not break
atoms. As a result, we can then assume all the edges between two vertices in a
same atom $K\in{\mathcal{K}}$ are $+$edges. The assumption only decreases
${\mathrm{opt}}$ and can only make the two properties of Theorem 14 harder to
satisfy. We use $K_{u}$ for every $u\in V$ to denote the atom that contains
$u$. We let $k_{u}=|K_{u}|$.

It is convenient for us to distribute the $+$edges incident to an atom
$K\in{\mathcal{K}}$ equally to the vertices in $K$. For every $u,v\in V$, we
define

$\displaystyle w_{uv}:=\frac{1}{k_{u}k_{v}}\sum_{u^{\prime}\in
K_{u},v^{\prime}\in K_{v}}1_{u^{\prime}v^{\prime}\in E^{+}}.$

to be the probability that an edge between a random vertex in $K_{u}$ and a
random vertex in $K_{v}$ is a $+$edge. So $w_{uv}\in[0,1]$ for every pair
$uv$; in particular, if $v\in K_{u}$, we have $w_{uv}=1$. We shall call
$w_{uv}$ the weight of the edge $uv$. For any set $u\in V,V^{\prime}\subseteq
V$, we define $w(u,V^{\prime}):=\sum_{v\in V^{\prime}}w_{uv}$ be the total
weight of edges between $u$ and $V^{\prime}$. Let $w_{u}:=w(u,V)$ be the total
weight of all edges incident to $u$. In this new instance, $w_{uv}$ fraction
of edge $uv$ has a $+$ sign, and the remaining $1-w_{uv}$ fraction has a $-$
sign; $w_{u}$ is the total fractional number of $+$edges incident to $u$,
which can be treated as the $+$degree of $u$. This new instance is equivalent
to the original one. Till the end of this section we focus on this instance
and call it the _averaged instance_ to distinguish it from the original one.

###  A.2 Defining Admissible Edges

In this section, we give a $(1+O(\varepsilon))$-approximate clustering
${\mathcal{C}}^{*}_{1}$ that does not break atoms. Then we define the set
$E_{\mathrm{adm}}$ of admissible edges so that all edges between two different
clusters in ${\mathcal{C}}^{*}_{1}$ are admissible. We shall bound
$|E_{\mathrm{adm}}|$ in terms of $\mathrm{obj}({\mathcal{K}})$, which is at
most $O(1)\cdot{\mathrm{opt}}$. Notice that the construction of
${\mathcal{C}}^{*}_{1}$ is not a part of our algorithm for Theorem 14, but the
definition of admissible edges is.

######  Lemma 69.

There is a clustering ${\mathcal{C}}^{*}_{1}$ of cost at most
$(1+O(\varepsilon)){\mathrm{opt}}$ that does not break any atom
$K\in{\mathcal{K}}$, and satisfies the following condition: For every $u,C$
with $K_{u}\subsetneq C\in{\mathcal{C}}^{*}_{1}$, we have
$w_{u,C}>\frac{|C|}{2}+\varepsilon\cdot w_{u}$.

###### Proof.

Start with ${\mathcal{C}}^{*}_{1}={\mathcal{C}}^{*}$; notice that it does not
break any atom. While the condition does not hold for some
$C\in{\mathcal{C}}^{*}_{1}$ and $u\in C$, i.e.,
$w_{u,C}\leq\frac{|C|}{2}+\varepsilon\cdot w_{u}$, we update
${\mathcal{C}}^{*}_{1}\leftarrow{\mathcal{C}}^{*}_{1}\setminus\\{C\\}\cup\\{C\setminus
K_{u},K_{u}\\}$. This finishes the construction of ${\mathcal{C}}^{*}_{1}$;
clearly it does not break any atom.

We then consider how much cost increment the procedure incurs. Focus on any
iteration of the while loop. At the beginning of the iteration, the cost of
edges incident to any vertex in $K_{u}$ in the clustering
${\mathcal{C}}^{*}_{1}$ (w.r.t the averaged instance) is

$\displaystyle\quad|C|-w(u,C)+w(u,V\setminus C)=w(u,V)+|C|-2w(u,C)\geq
w_{u}+|C|-2\left(\frac{|C|}{2}+\varepsilon\cdot
w_{u}\right)=(1-2\varepsilon)w_{u}.$

The inequalilty is by the condition of while loop.

The cost increment incurred by separating $K_{u}$ and $C\setminus K_{u}$ in
the iteration is

$\displaystyle\quad k_{u}\cdot\big{(}w(u,C\setminus K_{u})-(|C\setminus
K_{u}|-w(u,C\setminus K_{u}))\big{)}=k_{u}(2w(u,C\setminus K_{u})-|C\setminus
K_{u}|)$ $\displaystyle\leq k_{u}\cdot\big{(}2w(u,C)-|C|\big{)}\leq
2\varepsilon k_{u}\cdot w_{u}.$

Again, the second inequality is by the condition of the while loop.

We can charge the cost increment using the $(1-2\varepsilon)k_{u}\cdot w_{u}$
cost from edges incident to $u$: every unit cost is used to charge
$\frac{2\varepsilon}{1-2\varepsilon}$ unit cost increment. Notice that every
edge is charged at most twice. So, we have
$\mathrm{obj}({\mathcal{C}}^{*}_{1})-\mathrm{obj}({\mathcal{C}})\leq\frac{4\varepsilon}{1-2\varepsilon}\cdot\mathrm{obj}({\mathcal{C}}^{*}_{1})$.
This implies that
$\mathrm{obj}({\mathcal{C}}^{*}_{1})\leq\big{(}1+O(\varepsilon)\big{)}\mathrm{obj}({\mathcal{C}}^{*})=(1+O(\varepsilon)){\mathrm{opt}}$.
∎

We let ${\mathcal{C}}^{*}_{1}$ be the $(1+O(\varepsilon))$-approximate
clustering satisfying the properties of Lemma 69. We now proceed to the
definition of $E_{\mathrm{adm}}$; this should be independent of
${\mathcal{C}}^{*}_{1}$.

######  Lemma 70.

For every cluster $C\in{\mathcal{C}}^{*}_{1}$ and two vertices $u,v\in C$, we
have $w_{u}>\varepsilon w_{v}$.

###### Proof.

Assume $v\notin K_{u}$ since otherwise $w_{u}=w_{v}$. So $C$ contains both
$K_{u}$ and $K_{v}$. Lemma 69 implies $w_{u}\geq w_{u,C}>\frac{|C|}{2}$. On
the other hand, it implies $\varepsilon\cdot
w_{v}<w(v,C)-\frac{|C|}{2}\leq|C|-\frac{|C|}{2}=\frac{|C|}{2}$. Therefore,
$w_{u}>\varepsilon w_{v}$. ∎

Then, we define a set $E^{1}$ of edges so that $uv\in E^{1}$ if $\varepsilon
w_{v}<w_{u}<\frac{w_{v}}{\varepsilon}$; so $(V,E^{1})$ is undirected and
contains a self-loop $(u,u)$ for every $u\in V$. By Lemma 70, we have

######  Corollary 71.

Every $C\in{\mathcal{C}}^{*}_{1}$ forms a clique (with self-loops) in
$(V,E^{1})$.

Also, notice that $E^{1}$ may not be a subset of $E^{+}$. We use $N^{1}_{u}$
to denote the neighbor sets of $u$ in the graph $(V,E^{1})$.

######  Lemma 72.

For any cluster $C\in{\mathcal{C}}^{*}_{1}$, any two vertices $u,v\in C$ with
$v\notin K_{u}$ have $\sum_{p\in N^{1}_{u}\cap
N^{1}_{v}}w_{up}w_{vp}>\varepsilon\cdot(w_{u}+w_{v})$.

###### Proof.

Notice that $K_{u},K_{v}\subseteq C$. By Corollary 71, we have $C\subseteq
N^{1}_{u}$ and $C\subseteq N^{1}_{v}$. By Lemma 69, we have
$w(u,C)>\frac{|C|}{2}+\varepsilon w_{u}$, and
$w(v,C)>\frac{|C|}{2}+\varepsilon w_{v}$. Therefore,

$\displaystyle\sum_{p\in N^{1}_{u}\cap N^{1}_{v}}w_{up}w_{vp}$
$\displaystyle\geq\sum_{p\in C}w_{up}w_{vp}\geq\sum_{p\in
C}(w_{up}+w_{vp}-1)=w(u,C)+w(v,C)-|C|$
$\displaystyle>\frac{|C|}{2}+\varepsilon w_{u}+\frac{|C|}{2}+\varepsilon
w_{v}-|C|=\varepsilon(w_{u}+w_{v}).$

The second inequality is by that $w_{vp},w_{up}\in[0,1]$. ∎

Define a set $E^{2}$ of edges so that $uv\in E^{2}$ if and only if $v\in
K_{u}$, or the following holds: $uv\in E^{1}$ and $\sum_{p\in N^{1}_{u}\cap
N^{1}_{v}}w_{up}w_{vp}>\varepsilon(w_{u}+w_{v})$. Notice that $E^{2}\subseteq
E^{1}$. Corollary 71 and Lemma 72 implies

######  Corollary 73.

Every $C\in{\mathcal{C}}^{*}_{1}$ forms a clique (with self-loops) in
$(V,E^{2})$.

Let $d^{2}_{u}$ and $N^{2}_{u}$ denote the degree and neighbor set of $u$ in
the graph $(V,E^{2})$ respectively.

######  Lemma 74.

$d^{2}_{u}-k_{u}\leq O(\frac{1}{\varepsilon^{2}})(w_{u}-k_{u})$.

###### Proof.

Notice that $d^{2}_{u}-k_{u}$ is precisely the number of edges $uv\in E^{2}$
with $v\notin K_{u}$. Consider the graph $(V,E^{1})$ with edge weights $w$:
Every edge $vp\in E^{1}$ has weight $w_{vp}$. We define the weight of a
$2$-edge path $u$-$p$-$v$ in $(V,E^{1})$ to be $w_{up}w_{pv}$. By the
definition of $E^{2}$, if $v\notin K_{u}$, then $uv\in E^{2}$ only if the
total weight of $2$-edge paths of the form $u$-$p$-$v$ is at least
$\varepsilon(w_{u}+w_{v})>\varepsilon w_{u}$.

First, consider the paths $u$-$p$-$v$ with $p\notin K_{u}$. The total weight
of all such paths (over all $p$ and $v$) is at most
$(w_{u}-k_{u})\cdot\frac{w_{u}}{\varepsilon}$. This holds since the total
weight of edges between $u$ and $V\setminus K_{u}$ in the complete graph is
$w_{u}-k_{u}$, and any neighbor $p$ of $u$ in $(V,E^{1})$ has
$w_{p}<\frac{w_{u}}{\varepsilon}$ by the definition of $E^{1}$. Then consider
the paths $u$-$p$-$v$ with $p\in K_{u}$ and $v\notin K_{u}$. The total weight
of all such paths is at most $k_{u}(w_{u}-k_{u})$ as any $p\in K_{u}$ has
$w_{p}=w_{u}$ and $k_{p}=k_{u}$.

Therefore, the total number of verticies $v\notin K_{u}$ with $uv\in E^{2}$ is
at most

$\frac{(w_{u}-k_{u})\cdot\frac{w_{u}}{\varepsilon}+k_{u}(w_{u}-k_{u})}{\varepsilon
w_{u}}\leq\frac{1}{\varepsilon^{2}}(w_{u}-k_{u})+\frac{1}{\varepsilon}(w_{u}-k_{u})=O\big{(}\frac{1}{\varepsilon^{2}}\big{)}(w_{u}-k_{u}).\hfill\qed$

Therefore, we can define $uv$ to be admissible, i.e., in $E_{\mathrm{adm}}$,
if $uv\in E^{2}$ and $v\notin K_{u}$. This finishes the description of the
preclustered instance $({\mathcal{K}},E_{\mathrm{adm}})$. The total number of
admissible edges is

$\displaystyle|E_{\mathrm{adm}}|=\frac{1}{2}\sum_{u\in V}(d^{2}_{u}-k_{u})\leq
O\big{(}\frac{1}{\varepsilon^{2}}\big{)}\sum_{u\in
V}(w_{u}-k_{u})=O\big{(}\frac{1}{\varepsilon^{2}}\big{)}\cdot\mathrm{obj}({\mathcal{K}})\leq
O\big{(}\frac{1}{\varepsilon^{2}}\big{)}\cdot{\mathrm{opt}}.$

The second equality is by that
$\mathrm{obj}({\mathcal{K}})=\frac{1}{2}\sum_{u\in V}(w_{u}-k_{u})$ and the
last inequality is by Lemma 66. We can scale $\varepsilon$ down by a constant
at the beginning, so that the cost of ${\mathcal{C}}^{*}_{1}$ is at most
$(1+\varepsilon){\mathrm{opt}}$. This finishes the proof of Theorem 14.

##  Appendix B Detail of Lemma 60

We repeat the factor-revealing SDP for convenience.

$\min\qquad\sum_{I_{i},I_{j},I_{k},I_{l}}\sum_{T\in\mathcal{T_{D}}(I_{i},I_{j},I_{k},I_{l})}\eta_{T}\cdot\tilde{d}(I_{i},I_{j},I_{k},I_{l})\qquad\text{s.t.}$
(factor-revealing SDP) $\displaystyle
Q=\sum_{I_{i},I_{j},I_{k}}Head^{\intercal}(I_{i},I_{j},I_{k})\left(\sum_{I_{l},T\in\mathcal{T_{D}}(I_{i},I_{j},I_{k},I_{l})}\eta_{T}\cdot
C(T)\right)\cdot Tail(I_{i},I_{j},I_{k})\succeq 0$ $\displaystyle
F=\sum_{I_{i},I_{j},I_{k}}Head^{\intercal}(I_{i},I_{j},I_{k})\left(\sum_{I_{l},T\in\mathcal{T_{D}}(I_{i},I_{j},I_{k},I_{l})}\eta_{T}\cdot
A\right)\cdot Tail(I_{i},I_{j},I_{k})\succeq 0$ $\displaystyle\eta_{T}\geq
0\qquad\qquad\qquad\qquad\qquad\qquad\forall T\in\mathcal{T_{D}}$
$\displaystyle\sum_{T\in\mathcal{T_{D}}}\eta_{T}=1,\qquad\qquad\qquad\qquad\qquad\qquad$

We aim to demonstrate that ${\mathrm{OPT}_{\mathrm{SDP}}}=0$ for the budget
functions $b^{+}\equiv b^{+}_{1.437}$ and $b^{-}\equiv b^{-}_{1.437}$, where
${\mathrm{OPT}_{\mathrm{SDP}}}$ is the optimal value for factor-revealing SDP.
We describe the specific interval choices and small tricks employed to
expedite the computation of factor-revealing SDP.

We opt to divide the interval $[0,1]$ into 37 sub-intervals with the following
splitting points:

$\displaystyle[0.0,0.1,$ $\displaystyle
0.15,0.2,0.3,0.32,1/3,0.34,0.36,0.38,0.4,0.42,0.43,0.44,0.45,0.46,0.47,0.48,0.49,0.5,0.51,$
$\displaystyle
0.52,0.53,0.54,0.56,0.58,0.6,0.62,0.65,0.7,0.8,0.9,0.95,0.96,0.97,0.98,0.99,1]$

For intervals $I_{i},I_{j},I_{k}$ where $I_{i}\in[0.42,0.60]$ and
$I_{j}\in[0.42,0.60]$, we discretize the $y_{uvw}$ value. For each
$I_{i},I_{j},I_{k}$, we split the interval

$\displaystyle I_{l}=[max(0,(l(I_{i})+l(I_{j})+l(I_{k})-1)/2),r(I_{k})]$

into 10 sub-intervals, each with the same length. For triangles in different
ranges but with the same $y_{uv},y_{uw},y_{vw}$ value, they are treated as
different triangles since they affect different locations in the $Q$ matrix.
However, if two triangles have the same $y_{uv},y_{uw},y_{vw},y_{uvw}$ and are
located in the same $I_{i},I_{j},I_{k}$, but are located in different $I_{l}$
intervals, they can be treated as the same triangle since they affect $Q$ in
the same way. We may need to use different $\tilde{d}$ values to lower bound
$T$ when $T$ is in a different range. Assume $I^{(\tau)}_{l}$ and
$I^{(\tau+1)}_{l}$ share $y_{uvw}=r(I^{(\tau)}_{l})=l(I^{(\tau+1)}_{l})$
value. To lower bound $\Delta(T)-\text{cost}(T)$ in different ranges, we set
$\tilde{d}(T)=\min_{T_{1}\in\mathcal{T}(I_{i},I_{j},I_{k},I^{(\tau)}_{l})\cup\mathcal{T}(I_{i},I_{j},I_{k},I^{(\tau+1)}_{l})}\Delta(T_{1})-\text{cost}(T_{1})$.
This trick reduces the number of triangles to consider when discretizing
$y_{uvw}$, considering only 12 triangles instead of 20.

We choose to create numerous subintervals, especially around 0.5, to obtain
precise estimates for $+\\!+\\!-$ triangles with $y$ values of
$(y_{uv}=0.5,y_{uw}=0.5,y_{vw}=0,y_{uvw}=0)$ and $+\\!+\\!+$ triangles with
$y$ values of $(y_{uv}=0.5,y_{uw}=0.5,y_{vw}=0.5,y_{uvw}=0.5)$. When
determining the intervals, our strategy involves setting up a budget function
and identifying instances where ${\mathrm{OPT}_{\mathrm{SDP}}}$ becomes
negative, allowing us to refine the interval splitting for these problematic
cases.

Approximately 274,000 triangles are considered for the current interval
configuration. The SDP solver is executed on Google Cloud with N2 CPUs, taking
around 44,000 seconds to produce the ${\mathrm{OPT}_{\mathrm{SDP}}}$. It’s
important to note that loading all triangles into memory poses a bottleneck,
requiring approximately 200 GB of memory.

#### Lower bound of the factor-revealing SDP

One might wonder whether using more intervals and denser splitting of
$y_{uvw}$’s interval could demonstrate ${\mathrm{OPT}_{\mathrm{SDP}}}\geq 0$
for a smaller budget function. Unfortunately, even with more subintervals, a
significant improvement is not achievable if we only use $Q$ and $F$ as
constraints.

######  Lemma 75.

For the budget functions $b^{+}\equiv b^{+}_{1.421}$ and $b^{-}\equiv
b^{-}_{1.421}$, there does not exist intervals $I_{1},I_{2},...,I_{t}$ and
intervals for $y_{uvw}$ such that ${\mathrm{OPT}_{\mathrm{SDP}}}\geq 0$.

###### Proof.

Consider the $+\\!+\\!-$ triangle $T_{1}$ with $y$ value
$(y_{uv}=0.5,y_{uw}=0.5,y_{vw}=0,y_{uvw}=0)$ and $+\\!+\\!+$ triangles $T_{2}$
with $y$ values of $(y_{uv}=0.5,y_{uw}=0.5,y_{vw}=0.5,y_{uvw}=0.5)$. If
$\eta_{T_{1}}=0.75$ and $\eta_{T_{2}}=0.25$, both $Q$ and $F$ are PSD.
Additionally, $\Delta(T_{1})-\text{cost}(T_{1})\approx-0.1819$ and
$\Delta(T_{2})-\text{cost}(T_{2})\approx 0.54519$, leading to
${\mathrm{OPT}_{\mathrm{SDP}}}\leq\eta_{T_{1}}(\Delta(T_{1})-\text{cost}(T_{1}))+\eta_{T_{2}}(\Delta(T_{2})-\text{cost}(T_{2}))<0$.
∎

##  Appendix C Standard SDP Relaxation

The following is a natural SDP relaxation previously used in approximation
algorithms for the maximization problem [CGW05, Swa04] augmented with triangle
inequality from the standard LP relaxation.

$\displaystyle\min\quad\mathrm{obj}(x)=\sum_{ij\in E^{+}}x_{ij}$
$\displaystyle+\sum_{ij\in E^{-}}(1-x_{ij})$ (SDP) $\displaystyle x_{ij}$
$\displaystyle=1-v_{i}\cdot v_{j}\quad\forall i,j\in V$ $\displaystyle
v_{i}\cdot v_{j}$ $\displaystyle\geq 0\quad\forall i,j\in V$ $\displaystyle
v_{i}\cdot v_{i}$ $\displaystyle=1\quad\forall i\in V$ $\displaystyle x_{ij}$
$\displaystyle\leq x_{ik}+x_{jk}\quad\forall i,j,k\in V$ $\displaystyle v_{i}$
$\displaystyle\in\mathbb{R}^{n}\quad\forall i\in V.$

######  Lemma 76.

The integrality gap of (SDP) is at least $1.5$.

###### Proof.

Let $S_{k}$ be a star with $k$ leaves and one center vertex with degree $k$.
Here, the $\mathrm{sdp}_{k}$ value is for the basic relaxation. Then the value
${\mathrm{opt}}_{k}=k-1$. Consider the sdp solution where there are $k$ unit
vectors, one for each leaf, each with a 1 in the $i^{th}$ position. The vector
corresponding to the center vertex has length $k$ and each entry is
$1/\sqrt{k}$. Then the integrality gap is at least

$\displaystyle\frac{{\mathrm{opt}}_{k}}{\mathrm{sdp}_{k}}$
$\displaystyle=\frac{k-1}{k-\sqrt{k}}.$

Notice that for $k=2,3$, the above vector configuration leads to distances
that violate the triangle inequality. Thus the $k$ yielding the largest
integrality gap that also does not violate the triangle inequality is $k=4$,
which gives a gap of $3/2$. ∎