#  Understanding the Cluster LP for Correlation Clustering

Nairen Cao111Supported by NSF grant CCF-2008422.
Boston College
<EMAIL_ADDRESS>Vincent Cohen-Addad
Google Research
<EMAIL_ADDRESS>Euiwoong Lee222Supported in part by NSF grant
CCF-2236669 and Google.
University of Michigan
<EMAIL_ADDRESS>Shi Li 333Affiliated with the Department of Computer
Science and Technology in Nanjing University, and supported by the State Key
Laboratory for Novel Software Technology, and the New Cornerstone Science
Laboratory.
Nanjing University
<EMAIL_ADDRESS>Alantha Newman
Université Grenoble Alpes
<EMAIL_ADDRESS>Lukas Vogl
EPFL
<EMAIL_ADDRESS>
###### Abstract

In the classic Correlation Clustering problem introduced by Bansal, Blum, and
Chawla [BBC04], the input is a complete graph where edges are labeled either
$+$ or $-$, and the goal is to find a partition of the vertices that minimizes
the sum of the $+$edges across parts plus the sum of the $-$edges within
parts. In recent years, Chawla, Makarychev, Schramm and Yaroslavtsev [CMSY15]
gave a 2.06-approximation by providing a near-optimal rounding of the standard
LP, and Cohen-Addad, Lee, Li, and Newman [CLN22, CLLN23] finally bypassed the
integrality gap of 2 for this LP giving a $1.73$-approximation for the
problem.

While introducing new ideas for Correlation Clustering, their algorithm is
more complicated than typical approximation algorithms in the following two
aspects: (1) It is based on two different relaxations with separate rounding
algorithms connected by the round-or-cut procedure. (2) Each of the rounding
algorithms has to separately handle seemingly inevitable correlated rounding
errors, coming from correlated rounding of Sherali-Adams and other strong LP
relaxations [GS11, BRS11, RT12].

In order to create a simple and unified framework for Correlation Clustering
similar to those for typical approximate optimization tasks, we propose the
cluster LP as a strong linear program that might tightly capture the
approximability of Correlation Clustering. It unifies all the previous
relaxations for the problem. It is exponential-sized, but we show that it can
be $(1+\varepsilon)$-approximately solved in polynomial time for any
$\varepsilon>0$, providing the framework for designing rounding algorithms
without worrying about correlated rounding errors; these errors are handled
uniformly in solving the relaxation.

We demonstrate the power of the cluster LP by presenting a simple rounding
algorithm, and providing two analyses, one analytically proving a
$1.49$-approximation and the other solving a factor-revealing SDP to show a
$1.437$-approximation. Both proofs introduce principled methods by which to
analyze the performance of the algorithm, resulting in a significantly
improved approximation guarantee.

Finally, we prove an integrality gap of $4/3$ for the cluster LP, showing our
$1.437$-upper bound cannot be drastically improved. Our gap instance directly
inspires an improved NP-hardness of approximation with a ratio $24/23\approx
1.042$; no explicit hardness ratio was known before.

##  1 Introduction

Clustering is a classic problem in unsupervised machine learning and data
mining. Given a set of data elements and pairwise similarity information
between the elements, the task is to find a partition of the data elements
into clusters to achieve (often contradictory) goals of placing similar
elements in the same cluster and separating different elements in different
clusters. Introduced by Bansal, Blum, and Chawla [BBC04], Correlation
Clustering elegantly models such tension and has become one of the most widely
studied formulations for graph clustering. The input of the problem consists
of a complete graph $(V,E^{+}\uplus E^{-})$, where $E^{+}\uplus
E^{-}={V\choose 2}$, $E^{+}$ representing the so-called _positive_ edges and
$E^{-}$ the so-called _negative_ edges. The goal is to find a clustering
(partition) of $V$, namely $(V_{1},\dots,V_{k})$, that minimizes the number of
unsatisfied edges, namely the $+$edges between different clusters and the
$-$edges within the same cluster. Thanks to the simplicity and modularity of
the formulation, Correlation Clustering has found a number of applications,
e.g., finding clustering ensembles [BGU13], duplicate detection [ARS09],
community mining [CSX12], disambiguation tasks [KCMNT08], automated labelling
[AHK+09, CKP08] and many more.

This problem is APX-Hard [CGW05], and various $O(1)$-approximation algorithms
[BBC04, CGW05] have been proposed in the literature. Ailon, Charikar and
Newman introduced an influential pivot-based algorithm, which leads to a
combinatorial $3$-approximation and a $2.5$-approximation with respect to the
standard LP relaxation [ACN08]. The LP-based rounding was improved by Chawla,
Makarychev, Schramm and Yaroslavtsev to a $2.06$-approximation [CMSY15],
nearly matching the LP integrality gap of 2 presented in [CGW05].

It turns out that (a high enough level of) the Sherali-Adams hierarchy can be
used to design a strictly better than $2$-approximation. Cohen-Addad, Lee, and
Newman [CLN22] showed that $O(1/\varepsilon^{2})$ rounds of the Sherali-Adams
hierarchy have an integrality gap of at most $(1.994+\varepsilon)$. This
approximation ratio was improved by Cohen-Addad, Lee, Li, and Newman [CLLN23]
to $(1.73+\varepsilon)$ in $n^{{\mathrm{poly}}(1/\varepsilon)}$-time, which
combines pivot-based rounding and set-based rounding.

One undesirable feature of [CLLN23] is the lack of a single convex relaxation
with respect to which the approximation ratio is analyzed. For technical
reasons, it combines the two rounding algorithms via a generic round-or-cut
framework. Given $x\in[0,1]^{E}$, each of the two rounding algorithms outputs
either an integral solution with some guarantee or a hyperplane separating $x$
from the convex hull of integral solutions; if both algorithms output integral
solutions, one of them is guaranteed to achieve the desired approximation
factor. Though each of the rounding procedures is based on some LP
relaxations, they are different, so there is no single relaxation that can be
compared to the value of the final solution.

In this work, we propose the cluster LP as a single relaxation that captures
all of the existing algorithmic results. Based on this new unified framework,
we design a new rounding algorithm as well as principled tools for the
analysis that significantly extend the previous ones, ultimately yielding a
new approximation ratio of $1.437+\varepsilon$. The study of the cluster LP
sheds light on the hardness side as well, as we prove a $4/3\approx 1.33$ gap
for the cluster LP and a $24/23\approx 1.042$ NP-hardness of approximation.

###  1.1 Our Results

We first state the cluster LP here. It is similar to configuration LPs used
for scheduling and assignment problems [BS06, FGMS06]. In the cluster LP, we
have a variable $z_{S}$ for every $S\subseteq V,S\neq\emptyset$, that
indicates if $S$ is a cluster in the output clustering or not. As usual,
$x_{uv}$ for every $uv\in{V\choose 2}$ indicates if $u$ and $v$ are separated
in the clustering or not. For any $x\in[0,1]^{{V\choose 2}}$, we define
$\mathrm{obj}(x):=\sum_{uv\in E^{+}}x_{uv}+\sum_{uv\in E^{-}}(1-x_{uv})$ to be
the fractional number of edges in disagreement in the solution $x$.

$\min\qquad\mathrm{obj}(x)\qquad\text{s.t.}$ (cluster LP)
$\displaystyle\sum_{S\ni u}z_{S}$ $\displaystyle=1$ $\displaystyle\forall u\in
V$ (1) $\displaystyle\sum_{S\supseteq\\{u,v\\}}z_{S}$ $\displaystyle=1-x_{uv}$
$\displaystyle\forall uv\in{V\choose 2}$ (2) $\displaystyle z_{S}$
$\displaystyle\geq 0$ $\displaystyle\forall S\subseteq V,S\neq\emptyset$ (3)

The objective of the LP is to minimize $\mathrm{obj}(x)$, which is a linear
function. (1) requires that every vertex $u$ appears in exactly one cluster,
(2) gives the definition of $x_{uv}$ using $z$ variables.

The idea behind this LP was used in [CLLN23] to design their set-based
rounding algorithm, though the LP was not formulated explicitly in that paper.
Moreover, the paper did not provide an efficient algorithm to solve it
approximately. Our first result shows that we can approximately solve the
cluster LP in polynomial time, despite it having an exponential number of
variables. We remark that unlike the configuration LPs for many problems, we
do not know how to solve the cluster LP simply by considering its dual.

######  Theorem 1.

Let $\varepsilon>0$ be a small enough constant and ${\mathrm{opt}}$ be the
cost of the optimum solution to the given Correlation Clustering instance. In
time $n^{{\mathrm{poly}}(1/\varepsilon)}$, we can output a solution
$\big{(}(z_{S})_{S\subseteq V},(x_{uv})_{uv\in{V\choose 2}}\big{)}$ to the
cluster LP with $\mathrm{obj}(x)\leq(1+\varepsilon){\mathrm{opt}}$, described
using a list of non-zero coordinates. 444We remark that $\mathrm{obj}(x)$
given by the theorem is at most $1+\varepsilon$ times ${\mathrm{opt}}$,
instead of the value of the cluster LP. This is sufficient for our purpose.
One should also be able to achieve the stronger guarantee of
$(1+\varepsilon)$-approximation to the optimum fractional solution. Instead of
dealing with the optimum clustering ${\mathcal{C}}^{*}$ in the analysis, we
deal with the optimum fractional clustering to the LP. For simplicity, we
choose to prove the theorem with the weaker guarantee.

The cluster LP is the most powerful LP that has been considered for the
problem. Indeed, previous algorithms in [CLN22] and [CLLN23] can be
significantly simplified if one is given a $(1+\varepsilon)$-approximate
solution to the LP. A large portion of the algorithms and analysis in [CLN22]
and [CLLN23] is devoted to handle the additive errors incurred by the
correlated rounding procedure, which is inherited from the Raghavendra-Tan
rounding technique [RT12]. Instead, we move the complication of handling
rounding errors into the procedure of solving the cluster LP relaxation.

With this single powerful relaxation, we believe that Theorem 1 provides a
useful framework for future work that may use more ingenious rounding of the
exponential-sized cluster LP without worrying about errors. Indeed, the
constraints in the cluster LP imply that the matrix $(1-x_{uv})_{u,v\in V}$ is
PSD, 555Consider the matrix $Y\in[0,1]^{V\times V}$ where $y_{uv}=1-x_{uv}$
for every $u,v\in V$ ($Y_{uu}=1,\forall u\in V$). For every
$w\in\mathbb{R}^{V}$, we have $w^{T}Yw=\sum_{u,v\in
V}y_{uv}w_{u}w_{v}=\sum_{u,v}\sum_{S\supseteq\\{u,v\\}}z_{S}w_{u}w_{v}=\sum_{u,v}\sum_{S\subseteq
V}z_{S}\cdot(w_{u}\cdot 1_{u\in S})\cdot(w_{v}\cdot 1_{v\in
S})=\sum_{S\subseteq V}z_{S}\left(\sum_{u\in S}w_{u}\right)\left(\sum_{v\in
S}w_{v}\right)\geq 0$. and thus the LP is at least as strong as the natural
SDP for the problem. For the complementary version of maximizing the number of
correct edges, the standard SDP is known to give a better approximation
guarantee of $0.766$ [Swa04, CGW05]. For the minimization version, the
standard SDP has integrality gap at least 1.5 (see Appendix C), but it is
still open whether this program has an integrality gap strictly below 2 or
not.

We demonstrate the power of the cluster LP by presenting and analyzing the
following algorithm, significantly improving the previous best
$1.73$-approximation.

######  Theorem 2.

There exists a $(1.49+\varepsilon)$-approximation algorithm for Correlation
Clustering that runs in time $O(n^{{\mathrm{poly}}(1/\varepsilon)})$.

This is achieved by a key modification of the pivot-based rounding algorithm
that is used in conjunction with the set-based algorithm as in [CLLN23]. In
combination with more careful analysis, which involves principled methods to
obtain the best budget function, we obtain a significantly improved
approximation ratio.

In order to obtain an even tighter analysis of the same algorithm, we
introduce the new factor revealing SDP that searches over possible global
distributions of triangles in valid Correlation Clustering instances. By
numerically solving such an SDP, we can further improve the approximation
ratio of the same algorithm.

######  Theorem 3.

There exists a $(1.437+\varepsilon)$-approximation algorithm for Correlation
Clustering that runs in time $O(n^{{\mathrm{poly}}(1/\varepsilon)})$.

While the proof includes a feasible solution to a large SDP and is not human-
readable, we prove that our SDP gives an upper bound on the approximation
ratio, so it is a complete proof modulo the SDP feasibility of the solution.
Our program and solution can be found at
https://github.com/correlationClusteringSDP/SDP1437code/.

We also study lower bounds and prove the following lower bound on the
integrality gap of the cluster LP.

######  Theorem 4.

For any $\varepsilon>0$, the integrality gap of the cluster LP is at least
$4/3-\varepsilon$.

This integrality gap for the cluster LP, after some (well-known) loss,
directly translates to NP-hardness. Apart from the APX-hardness [CGW05], it is
the first hardness with an explicit hardness ratio.

######  Theorem 5.

Unless $\mathbf{P}=\mathbf{BPP}$, for any $\varepsilon>0$, there is no
$(24/23-\varepsilon)$-approximation algorithm for Correlation Clustering.

###  1.2 Further Related Work

The weighted version of Correlation Clustering, where each pair of vertices
has an associated weight and unsatisfied edges contribute a cost proportional
to their weight to the objective, is shown to be equivalent to the Multicut
problem [DEFI06], implying that there is an $O(\log n)$-approximation but no
constant factor approximation is possible under the Unique Games Conjecture
[CKK+06].

In the unweighted case, a PTAS exists when the number of clusters is a fixed
constant [GG06, KS09]. Much study has been devoted to the minimization version
of Correlation Clustering in various computational models, for example in the
online setting [MSS10, LMV+21, CLMP22], as well as in other practical settings
such as distributed, parallel or streaming [CDK14, ACG+15, CLM+21, PPO+15,
CCMU21, Vel22, VGW18, AW22, BCMT22, BCMT23, CHS24, CM23, CKL+24]. Other recent
work involves settings with fair or local guarantees [AN23, DMN23, HIA23].

##  2 Algorithmic Framework and Setup for Analysis

In this section, we describe our algorithm for obtaining the improved
approximation ratio for Correlation Clustering. We solve the cluster LP using
Theorem 1 to get a fractional solution $z=(z_{S})_{S\subseteq V}$, which
determines $x\in[0,1]^{V\choose 2}$ as in (2):
$x_{uv}:=1-\sum_{S\supseteq\\{u,v\\}}z_{S}$ for every $uv\in{V\choose 2}$. We
have $\mathrm{obj}(x)\leq(1+\varepsilon){\mathrm{opt}}$. The theorem will be
proved in Section 4. With $z$, we then run two procedures: the cluster-based
rounding and the pivot-based rounding with threshold $1/3$. We select the
better result as the final clustering. The two procedures are defined in
Algorithms 1 and 2 respectively. We use $N^{+}(u)$ and $N^{-}(u)$ to denote
the sets of $+$ and $-$neighbors of a vertex $u\in V$ respectively.

Algorithm 1 Cluster-Based Rounding

1:${\mathcal{C}}\leftarrow\emptyset,V^{\prime}\leftarrow V$

2:while $V^{\prime}\neq\emptyset$ do

3: randomly choose a cluster $S\subseteq V$, with probabilities
$\frac{z_{S}}{\sum_{S^{\prime}}z_{S^{\prime}}}$

4: if $V^{\prime}\cap S\neq\emptyset$ then
${\mathcal{C}}\leftarrow{\mathcal{C}}\cup\\{V^{\prime}\cap S\\}$,
$V^{\prime}\leftarrow V^{\prime}\setminus S$

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

Algorithm 2 Pivot-Based Rounding with Threshold $1/3$

1:${\mathcal{C}}\leftarrow\emptyset,V^{\prime}\leftarrow V$

2:while $V^{\prime}\neq\emptyset$ do

3: randomly choose a pivot $u\in V^{\prime}$

4: $C\leftarrow\\{v\in V^{\prime}\cap N^{+}(u):x_{uv}\leq\frac{1}{3}\\}$

5: for every $v\in V^{\prime}\cap N^{-}(u)$ do independently add $v$ to $C$
with probability $1-x_{uv}$

6: randomly choose a set $S\ni u$, with probabilities $z_{S}$ $\triangleright$
We have $\sum_{S\ni u}z_{S}=1$

7: $C\leftarrow C\cup(S\cap V^{\prime}\cap N^{+}(u))$,
${\mathcal{C}}\leftarrow{\mathcal{C}}\cup\\{C\\}$, $V^{\prime}\leftarrow
V^{\prime}\setminus C$

8:return ${\mathcal{C}}$

#### Analysis of Cluster-Based Rounding Procedure.

The cluster-based rounding procedure is easy to analyze. The following lemma
suffices.

######  Lemma 6.

For every $uv\in{V\choose 2}$, the probability that $u$ and $v$ are separated
in the clustering ${\mathcal{C}}$ output by the cluster-based rounding
procedure is $\frac{2x_{uv}}{1+x_{uv}}$. So the probability they are in the
same cluster is $\frac{1-x_{uv}}{1+x_{uv}}$.

###### Proof.

We consider the first set $S$ chosen in the cluster-based rounding algorithm
such that $\\{u,v\\}\cap S\neq\emptyset$. $u$ and $v$ will be separated iff
$|S\cap\\{u,v\\}|=1$. The probability that this happens is precisely
$\frac{\sum_{|S\cap\\{u,v\\}|=1}z_{S}}{\sum_{S\cap\\{u,v\\}\neq\emptyset}z_{S}}=\frac{2x_{uv}}{1+x_{uv}}$.
∎

Therefore, a $+$edge $uv$ will incur a cost of $\frac{2x_{uv}}{1+x_{uv}}$ in
expectation in the cluster-based rounding procedure, and a $-$edge will incur
a cost of $\frac{1-x_{uv}}{1+x_{uv}}$. The approximation ratios for a $+$edge
$uv$ and a $-$edge $uv$ are respectively $\frac{2}{1+x_{uv}}$ and
$\frac{1}{1+x_{uv}}$. Notice that the latter quantity is at most $1$.

#### Notations and Analysis for Pivot-Based Rounding Procedure.

We now proceed to the pivot-based rounding procedure in Algorithm 2. We remark
that to recover the correlated rounding algorithm in [CLN22] and [CLLN23], we
can use $C\leftarrow\emptyset$ in Step 4. Then we can obtain their
approximation ratios without the complication of handling rounding errors. The
errors are handled in [CLN22] by distinguishing between the short, median and
long $+$edges. In our algorithm, we also distinguish between _short_ $+$edges
(those with $x_{uv}\leq\frac{1}{3}$) and _long_ $+$edges (those with
$x_{uv}>\frac{1}{3}$); however, the purpose of this distinction is to get an
improved approximation ratio, instead of to bound the rounding errors.

Our high-level setup of the analysis follows from [CLN22, CLLN23], which in
turn is based on [ACN08] and [CMSY15]. We consider a general budget for every
edge. We shall define two _budget functions_ :

  * •

$b^{+}:[0,1]\to\mathbb{R}_{\geq 0}$ and $b^{-}:[0,1]\to\mathbb{R}_{\geq 0}$.

They determine the _budget_ $b_{uv}$ for the edge $uv$: if $uv\in E^{+}$, then
$b_{uv}:=b^{+}(x_{uv})$, and if $uv\in E^{-}$, then $b_{uv}:=b^{-}(x_{uv})$.

We now focus on one iteration of the while loop in Algorithm 2. Suppose
$u,v,w\in V^{\prime}$ at the beginning of the iteration, and let $C$ be the
cluster constructed at the end. We use $u$ to denote the event that $u$ is
chosen as the pivot. We say $vw$ incurs a cost in the iteration, if $vw\in
E^{+}$ and $|C\cap\\{v,w\\}|=1$, or $vw\in E^{-}$ and $\\{v,w\\}\subseteq C$.
Then, we define

$\displaystyle\mathrm{cost}_{u}(v,w):=\Pr[vw\text{ incurs a cost}\mid u].$

and

$\displaystyle\Delta_{u}(v,w):=\Pr[C\cap\\{v,w\\}\neq\emptyset\mid u]\cdot
b_{vw}.$

$\mathrm{cost}_{u}(v,w)$ is the probability that $vw$ incurs a cost
conditioned on the event $u$. When an edge $vw$ disappears, we say $vw$
_releases_ its budget. So, $\Delta_{u}(v,w)$ is the expected budget released
by $vw$ in the iteration when $u$ is the pivot. Notice that both
$\mathrm{cost}_{u}(v,w)$ and $\Delta_{u}(v,w)$ do not depend on $V^{\prime}$,
provided that $u,v,w\in V^{\prime}$.

We call a set of three distinct vertices a triangle. A set of two distinct
vertices is called a degenerate triangle. For triangle $(u,v,w)$, let

$\displaystyle\mathrm{cost}(u,v,w):=\mathrm{cost}_{u}(v,w)+\mathrm{cost}_{v}(u,w)+\mathrm{cost}_{w}(u,v),\quad\text{and}\quad\Delta(u,v,w):=\Delta_{u}(v,w)+\Delta_{v}(u,w)+\Delta_{w}(u,v).$

For degenerate triangle $(u,v)$, let

$\displaystyle\mathrm{cost}(u,v):=\mathrm{cost}_{u}(u,v)+\mathrm{cost}_{v}(u,v),\quad\text{and}\quad\Delta(u,v):=\Delta_{u}(u,v)+\Delta_{v}(u,v).$

######  Lemma 7.

Suppose that for every $V^{\prime}\subseteq V$, we have

$\displaystyle\sum_{(u,v,w)\in\binom{V^{\prime}}{3}}\mathrm{cost}(u,v,w)+\sum_{(u,v)\in\binom{V^{\prime}}{2}}\mathrm{cost}(u,v)\leq\sum_{(u,v,w)\in\binom{V^{\prime}}{3}}\Delta(u,v,w)+\sum_{(u,v)\in\binom{V^{\prime}}{2}}\Delta(u,v).$
(4)

Then, the expected cost of the clustering output by Algorithm 2 is at most
$\sum_{uv\in{V\choose 2}}b_{uv}$.

###### Proof.

Focus on any iteration of Algorithm 2; $V^{\prime}$ is the $V^{\prime}$ at the
beginning of the iteration.

The expected cost incurred by all edges in the iteration is

$\displaystyle\frac{1}{|V^{\prime}|}\sum_{u\in
V^{\prime}}\sum_{(v,w)\in{V^{\prime}\choose
2}}\mathrm{cost}_{u}(v,w)\frac{1}{|V^{\prime}|}\sum_{(u,v,w)\in{V^{\prime}\choose
3}}\mathrm{cost}(u,v,w)+\frac{1}{|V^{\prime}|}\sum_{(u,v)\in{V^{\prime}\choose
2}}\mathrm{cost}(u,v).$

The expected budget released at this iteration is

$\displaystyle\frac{1}{|V^{\prime}|}\sum_{u\in
V^{\prime}}\sum_{(v,w)\in{V^{\prime}\choose
2}}\Delta_{u}(v,w)=\frac{1}{|V^{\prime}|}\sum_{(u,v,w)\in{V^{\prime}\choose
3}}\Delta(u,v,w)+\frac{1}{|V^{\prime}|}\sum_{(u,v)\in{V^{\prime}\choose
2}}\Delta(u,v).$

Therefore, if the condition of the lemma holds, then at every iteration of
Algorithm 2, the expected cost incurred is at most the expected budget
released. Overall, the expected cost of the final clustering is at most the
expected total budget released by all edges during the whole procedure, which
is $\sum_{uv\in{V\choose 2}}b_{uv}$. This finishes the proof of the lemma. ∎

To obtain an approximation ratio of $\alpha\in[1,2)$, we consider a variant of
our algorithm, in which we run the cluster-based rounding procedure (Algorithm
1) with probability $\frac{\alpha}{2}$, and the pivot-based rounding procedure
with threshold $1/3$ (Algorithm 2) with the remaining probability
$1-\frac{\alpha}{2}$. Clearly, the actual algorithm that picks the better of
the two clusterings generated can only be better. We set up the budget
functions $b^{+}$ and $b^{-}$ such that every edge pays a cost of at most
$\alpha$ times its LP cost in expectation. That is, the following properties
are satisfied for every $x\in[0,1]$:

$\displaystyle\frac{\alpha}{2}\cdot\frac{2x}{1+x}+\left(1-\frac{\alpha}{2}\right)b^{+}(x)=\alpha
x,\qquad\frac{\alpha}{2}\cdot\frac{1-x}{1+x}+\left(1-\frac{\alpha}{2}\right)b^{-}(x)=\alpha(1-x).$

This gives us the following definitions:

$\displaystyle
b^{+}_{\alpha}(x):=\frac{\alpha}{1-\alpha/2}\cdot\frac{x^{2}}{1+x},\qquad\text{and}\qquad
b^{-}_{\alpha}(x):=\frac{\alpha}{1-\alpha/2}\cdot\frac{(1+2x)(1-x)}{2(1+x)},\qquad\forall
x\in[0,1].$ (5)

######  Lemma 8.

If the budget functions $b^{+}_{\alpha}$ and $b^{-}_{\alpha}$ satisfy (4) for
some $\alpha\in[1,2)$, then our algorithm has an approximation ratio of
$\alpha$.

###### Proof.

Consider the variant of the algorithm where we run the cluster-based rounding
procedure with probability $\frac{\alpha}{2}$, and the pivot-based procedure
with threshold $1/3$ with the remaining probability of $1-\frac{\alpha}{2}$.
By Lemma 7, the expected cost of the clustering given by the variant is at
most

$\displaystyle\quad\sum_{uv\in
E^{+}}\left(\frac{\alpha}{2}\cdot\frac{2x_{uv}}{1+x_{uv}}+\big{(}1-\frac{\alpha}{2}\big{)}\cdot
b^{+}_{\alpha}(x_{uv})\right)+\sum_{uv\in
E^{-}}\left(\frac{\alpha}{2}\cdot\frac{1-x_{uv}}{1+x_{uv}}+\big{(}1-\frac{\alpha}{2}\big{)}\cdot
b^{-}_{\alpha}(x_{uv})\right)$ $\displaystyle=\alpha\left(\sum_{uv\in
E^{+}}x_{uv}+\sum_{uv\in E^{-}}(1-x_{uv})\right)=\alpha\cdot\mathrm{obj}(x).$

The actual algorithm we run can only be better than this variant. ∎

As a baseline, we provide a per-triangle analysis leading to an approximation
ratio of $1.5$ in Section 5:

######  Lemma 9.

For budget functions $b^{+}\equiv b^{+}_{1.5}$ and $b^{-}\equiv b^{-}_{1.5}$,
we have $\mathrm{cost}(T)\leq\Delta(T)$ for every triangle $T$.

Clearly, the lemma implies that (4) holds for $b^{+}\equiv b^{+}_{1.5}$ and
$b^{-}\equiv b^{-}_{1.5}$. By Lemma 8, our algorithm gives an approximation
ratio of $1.5$. We remark that $1.5$ is the best possible ratio we can achieve
using the per-triangle analysis. For a $+\\!+\\!-$ triangle with length
$\frac{1}{2}$ for $+$edges and length $1$ for the $-$edge, we need to pay a
factor of $2$ for each of the $\frac{1}{2}$-length $+$edge. Then the cluster-
based rounding algorithm gives factors of $2$ and $\frac{4}{3}$ for $+$edges
of lengths $0$ and $\frac{1}{2}$ respectively. For the pivot-based rounding
algorithm, the factors are at least $0$ and $2$. A combination of the two
algorithms can only lead to a factor of $1.5$.

To get a better approximation ratio, we provide two analyses that use global
distributions of triangles. The former is purely analytic and the latter
relies on solving a factor-revealing SDP. The following two lemmas are proved
in Sections 6 and 7 respectively.

######  Lemma 10.

(4) holds for budget functions $b^{+}\equiv b^{+}_{1.49}$ and $b^{-}\equiv
b^{-}_{1.49}$.

######  Lemma 11.

(4) holds for budget functions $b^{+}\equiv b^{+}_{1.437}$ and $b^{-}\equiv
b^{-}_{1.437}$.

Combined with Lemma 8, the two lemmas imply Theorems 2 and 3 respectively.

##  3 Overview of Techniques

In this section, we provide overviews of the techniques used in our results.

#### Simpler and Better Preclustering Procedure.

The concept of preclustering was introduced in [CLLN23]. In a preclustered
instance, we predetermine the fate of some edges: for some edges $uv$, $u$ and
$v$ must be in the same cluster; for some other edges $uv$, $u$ and $v$ must
be separated. Since the relation of being in the same cluster is transitive,
we define a preclustered instance using a pair
$({\mathcal{K}},E_{\mathrm{adm}})$, where ${\mathcal{K}}$ is a partition of
$V$ into so called _atoms_ and $E_{\mathrm{adm}}\subseteq{V\choose 2}$ is a
set of _admissible_ edges. An atom can not be broken. If $u$ and $v$ are not
in the same atom and $uv\notin E_{\mathrm{adm}}$, then $u$ and $v$ must be
separated. [CLLN23] showed how to construct a preclustered instance
$({\mathcal{K}},E_{\mathrm{adm}})$, losing only a $(1+\varepsilon)$ factor in
the optimum cost, while at the same time guaranteeing that
$|E_{\mathrm{adm}}|\leq O({\mathrm{opt}}/\varepsilon^{12})$. This is crucial
for their correlated rounding algorithm, as it loses an additive error
depending on $|E_{\mathrm{adm}}|$. In this work, we still need the
preclustering procedure to bound the rounding error, but now it is inside the
procedure of solving the cluster LP.

We greatly simplify the preclustering procedure from [CLLN23], and as a
result, we achieve a much better bound of $O({\mathrm{opt}}/\varepsilon^{2})$
on $|E_{\mathrm{adm}}|$. [CLLN23] used the agreement graph to construct the
atoms; roughly speaking, two vertices are in agreement if their neighborhood
sets are similar to each other. The analysis uses many technical structural
lemmas from [CLM+21], which solves Correlation Clustering in the online
setting. In contrast, our construction of atoms is simple: we construct an
$O(1)$-approximate clustering ${\mathcal{C}}$, mark vertices whose costs are
large, and then ${\mathcal{K}}$ is obtained from ${\mathcal{C}}$ by removing
marked vertices and creating singletons for them. The set of admissible edges
is roughly defined as follows: we construct a graph $(V,E^{1})$ where two
vertices are neighbors if their $+$degrees are similar. Then an edge $uv$ is
admissible if $u$ and $v$ have many common neighbors in $E^{+}\cap E^{1}$.

#### Solving Cluster LP by Preclustering.

As we mentioned, we move the complication of handling rounding errors to the
step of solving the cluster LP. As in [CLLN23], we construct a preclustered
instance $({\mathcal{K}},E_{\mathrm{adm}})$, and formulate an LP relaxation
aimed at finding the $(1+\varepsilon)$-approximate _good clustering_ for
$({\mathcal{K}},E_{\mathrm{adm}})$, that we call the _bounded sub-cluster LP_.
In contrast to [CLLN23], which solves many instances of this LP embedded in
their round-or-cut framework, we only solve the LP once, therefore avoiding
this heavy framework. With a solution $(x,y)$ to the LP, we run a procedure
that constructs a single cluster $C$ randomly. The probability that any vertex
is in $C$ is precisely $1/y_{\emptyset}$, where $y_{\emptyset}$ is the
fractional number of clusters in $y$. The probabilities that exactly one of
$u$ and $v$ is in $C$, and both of them are in $C$, are respectively
$\frac{x_{uv}}{y_{\emptyset}}$ and $\frac{1-x_{uv}}{y_{\emptyset}}$ up to some
error terms arising from the Raghavendra-Tan rounding procedure. As usual,
$x_{uv}$ is the extent in which $u$ and $v$ are separated.

To construct the solution $z=(z_{S})_{S\subseteq V}$ for the cluster LP, we
generate $y_{\emptyset}\Delta$ many clusters $C$ independently, for a large
enough polynomial $\Delta$. Roughly speaking, the solution $z$ is
$\frac{1}{\Delta}$ times the multi-set of clusters $C$ we generated. The error
incurred by the Raghavendra-Tan rounding procedure can be bounded in terms of
$|E_{\mathrm{adm}}|$, and the error from sampling can be bounded using
concentration bounds.

#### 1.49-approximation.

We start with the algorithm of [CLLN23], but make several key modifications
both in the design and in the analysis. This allows us to significantly
improve the approximation ratio, first to 1.5 and, eventually, to 1.49, which
shows that, perhaps surprisingly, even the rather low approximation factor of
$1.5$ is not tight for Correlation Clustering. The first key ingredient is to
use a principled budget function for the pivot-based rounding procedure,
defined earlier in (5), which is designed to optimally balance the
approximation factor of edges between the two rounding procedures. This new
budget function is better than the one used in [CLLN23], but does not allow us
to reach 1.5 without changing the algorithm. Indeed, the budget for the short
$+$edges in $+\\!+\\!+$ triangles is still too low to reach the approximation
ratio 1.5. Thus, the second key ingredient is to add the threshold step to the
pivot-based rounding procedure for the short $+$edges (i.e., $+$edges $uv$
with $x_{uv}\leq 1/3$). By adding this threshold step, the cost of the
triangles containing such edges decreases; for example, a $+\\!+\\!+$ triangle
with all short edges now has cost zero. This allows us to use the new budget
function and still reach 1.5. Notice that making the threshold too large would
result in too much cost for $+\\!+\\!-$ triangles.

Finally, we observe that, analogous to the correlated rounding approach of
[CLN22], only the _bad triangles_ are tight, meaning their cost equals their
budget. Roughly speaking, a bad triangle is a $+\\!+\\!-$ triangle whose two
$+$edges have value very close to half and whose $-$edge has value close to
one. This allows us to apply a charging argument, in which tight triangles
have part of their cost paid for by triangles that are not tight (i.e., that
have extra budget). Now there are no tight triangles (i.e., all triangles have
some unused budget), and we can decrease the $\alpha$ in the budget function
from $1.5$ to $70/47$. As previously [ACN08, CMSY15, CLN22, CLLN23], the
analysis necessary to reach 1.5 and go below requires a case-by-case analysis
of triangle types to ensure that the budget allocated to each triangle covers
its cost. Both the new threshold step and the new budget functions result in
an analysis that is more involved than what was required in [CLLN23], but is
still feasible.

#### 1.437-approximation.

The above charging argument between different types of triangles can be more
systematically expressed by a factor-revealing SDP. Given a cluster LP
solution $z_{S}$ and vertices $u,v,w$, let us define
$y_{uv}:=\sum_{S\supseteq\\{u,v\\}}z_{S}$ (resp.
$y_{uvw}:=\sum_{S\supseteq\\{u,v,w\\}}z_{S})$ be the probability that $u,v$
(resp. $u,v,w$) are in the same cluster. Given any quadruple
$T=(a,b,c,d)\in[0,1]^{4}$, let $\eta_{T}$ represent the number of triangles
$(u,v,w)$ such that of $y_{uv}=a,y_{uw}=b,y_{vw}=c,y_{uvw}=d$. The above
1.49-approximation analysis can be regarded as putting one constraint on the
distribution of $\eta_{T}$. To enhance the approximation ratio and reduce the
budget function, we opt for a more detailed categorization of triangles,
imposing stronger constraints on $\eta_{T}$.

Consider an imaginary rounding procedure, where given a pivot $u$, the cluster
$C$ that contains $u$ is simply chosen with probability $z_{C}$ (note that
$\sum_{C\ni u}z_{C}=1$). Let $X_{v}$ denote the event that node $v$ is
included in the cluster of node $u$ in this rounding. We can show
$\operatorname*{{\mathbb{E}}}[X_{v}\cdot X_{w}]=y_{uvw}$ and
$\operatorname*{{\mathbb{E}}}[X_{v}]\cdot\operatorname*{{\mathbb{E}}}[X_{w}]=y_{uv}y_{uw}$.
The covariance matrix $COV_{u}$, where
$COV_{u}(v,w)=\operatorname*{{\mathbb{E}}}[X_{v}\cdot
X_{w}]-\operatorname*{{\mathbb{E}}}[X_{v}]\cdot\operatorname*{{\mathbb{E}}}[X_{w}]=y_{uvw}-y_{uv}y_{uw}$,
must be positive semidefinite (PSD). This PSD constraint on the covariance
matrix enforces a stronger constraint on $\eta_{T}$. For instance, if all non-
degenerate triangles centered at $u$ are $+\\!+\\!-$ triangles with $y$ value
$(y_{uv}=0.5,y_{uw}=0.5,y_{wv}=0,y_{uvw}=0)$, then the covariance matrix of
$COV_{u}$ cannot be PSD because $COV_{u}(v,w)=y_{uvw}-y_{uv}y_{uw}=-0.25$ for
almost all non-diagonal entries.

For a triangle $T=(y_{uv},y_{uw},y_{vw},y_{uvw})$, we discretize
$y_{uv},y_{uw},y_{vw}$ to incorporate the PSD constraint. We partition the
interval $[0,1]$ into numerous subintervals $I_{1},I_{2},...,I_{t}$. Each
triangle with $y$ value $(y_{uv}\in I_{i},y_{uw}\in I_{j},y_{vw}\in
I_{k},y_{uvw})$ is placed in one of these interval combinations. We can
rearrange $COV_{u}$ as $Q_{u}\in\mathbb{R}^{t\times t}$, where
$Q_{u}(I_{i},I_{j})=\sum_{y_{uv}\in I_{i},y_{uw}\in
I_{j}}(y_{uvw}-y_{uv}y_{uw})$. Considering $Q=\sum_{u\in V}Q_{u}$, we can
represent $Q$ using $T$ and $\eta_{T}$. The PSD property of $Q_{u}$ implies
$Q$ is PSD, thus enforcing a constraint on $\eta_{T}$.

Despite there being infinitely many types of triangles in each range
$I_{i},I_{j},I_{k}$, our key observation is that $y_{uvw}-y_{uv}y_{uw}$ is
multi-linear. Therefore, we only need a few triangles in each range to
represent all possible triangles. We want to mention the triangles we need are
fixed so can be precomputed and the only unsure variable is $\eta_{T}$. To
compute a lower bound $\sum\eta_{T}(\Delta(T)-\text{cost}(T))$, we set up a
semi-definite program (SDP) under the constraint that $Q$ is PSD. This SDP is
independent of cluster LP and relies on the chosen interval and budget
function. By employing a practical SDP solver, we demonstrate that
$\sum\eta_{T}(\Delta(T)-\text{cost}(T))\geq 0$.

#### Gaps and Hardness.

A high-level intuition for the cluster LP is the following: (any) LPs cannot
distinguish between a random graph and a nearly bipartite graph. For the
cluster LP, given a complete graph $H=(V_{H},E_{H})$ with $n=|V_{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$. Consider
vertices of $H$ as ideal clusters in $G$ containing their incident edges. The
LP fractionally will think that it is nearly bipartite, implying that the
entire $E_{H}$ can be partitioned into $n/2$ ideal clusters of the same size.
Of course, integrally, such a partition is not possible in complete 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].

The idea for the NP-hardness of approximation is the same. The main
difference, which results in a worse factor here, is that other polynomial-
time algorithms (e.g., SDPs) can distinguish between random and nearly
bipartite graphs! 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 hardness result of Cohen-Addad, Karthik, and
Lee [CAL22] that shows that it is hard to distinguish whether $H$ is nearly
bipartite, which implies that half of the vertices intersect every hyperedge,
or close to a random hypergraph.

#### Organization.

We show how to solve the cluster LP in Section 4, proving Theorem 1. It uses
our improved preclustering procedure, which will be described in Section A. We
prove Lemmas 9, 10 and 11 in Sections 5, 6 and 7 respectively; they will prove
Theorems 2 and 3. We give the $(\frac{4}{3}-\varepsilon)$-integrality gap of
the cluster LP (Theorem 4) in Section 8, and the improved hardness of
$24/23-\varepsilon$ (Theorem 5) in Section 9.

#### Global Notations.

For two sets $A$ and $B$, we use $A\triangle B=(A\setminus B)\cup(B\setminus
A)$ to denote the symmetric difference between $A$ and $B$. We used
$N^{+}_{u}$ and $N^{-}_{u}$ to denote the sets of $+$ and $-$neighbors of a
vertex $u$ respectively in the Correlation Clustering instance. For a
clustering ${\mathcal{C}}$ of $V$, we define $\mathrm{obj}({\mathcal{C}})$ to
be the objective value of ${\mathcal{C}}$. For any $x\in[0,1]^{{V\choose 2}}$,
we already defined $\mathrm{obj}(x)=\sum_{uv\in E^{+}}x_{uv}+\sum_{uv\in
E^{-}}(1-x_{uv})$. Recall that we defined
$\mathrm{cost}_{u}(v,w),\Delta_{u}(v,w),\mathrm{cost}(T)$ and $\Delta(T)$ for
a triangle $T=(u,v,w)$ or a degenerate triangle $T=(u,v)$ in Section 2; they
depend on the budget functions $b^{+}$ and $b^{-}$.

##  4 Solving Cluster LP Relaxation Approximately

In this section, we show how to solve the cluster LP in polynomial time, by
proving Theorem 1, which is repeated below. See 1

We define some global parameters used across this section. Let
$\varepsilon_{1}=\varepsilon^{3},\varepsilon_{\mathrm{rt}}=\varepsilon_{1}^{2}=\varepsilon^{6}$,
and $r=\Theta(1/\varepsilon_{\mathrm{rt}}^{2})=\Theta(1/\varepsilon^{12})$ be
an integer, with some large enough hidden constant. The subscript “rt” stands
for Raghavendra-Tan.

###  4.1 Preclustering

We use the definition of a preclustered instance from [CLLN23], with some
minor modifications.

######  Definition 12.

Given a Correlation Clustering instance $(V,E^{+}\uplus E^{-})$, a
preclustered instance is defined by a pair $({\mathcal{K}},E_{\mathrm{adm}})$,
where ${\mathcal{K}}$ is a partition of $V$ (which can also be viewed as a
clustering), and $E_{\mathrm{adm}}\subseteq\binom{V}{2}$ is a set of pairs
such that for every $uv\in E_{\mathrm{adm}}$, $u$ and $v$ are not in a same
set in ${\mathcal{K}}$.

Each set $K\in{\mathcal{K}}$ is called an atom. An (unordered) pair $uv$
between two vertices $u$ and $v$ in a same $K\in{\mathcal{K}}$ is called an
atomic edge; in particular, a self-loop $uu$ is an atomic edge. A pair that is
neither an atomic nor an admissible edge is called a _non-admissible_ edge.

There are two minor differences between our definition and the one in
[CLLN23]. First, we require that ${\mathcal{K}}$ forms a partition; this can
be guaranteed by adding singletons. Second, we do not require an edge between
two different non-singleton atoms to be non-admissible. Our construction can
guarantee this condition, but it is not essential.

######  Definition 13.

Given a preclustered instance $({\mathcal{K}},E_{\mathrm{adm}})$ for some
Correlation Clustering instance $(V,E^{+}\uplus E^{-})$, a clustering
${\mathcal{C}}$ of $V$ is called good with respect to
$({\mathcal{K}},E_{\mathrm{adm}})$ if

  * •

$u$ and $v$ are in the same cluster in ${\mathcal{C}}$ for an atomic edge
$uv$, and

  * •

$u$ and $v$ are not in the same cluster in ${\mathcal{C}}$ for a non-
admissible edge $uv$.

The following theorem with a worse bound on $|E_{\mathrm{adm}}|$ was proved in
[CLLN23]. We give a cleaner proof of the theorem in Section A; as a byproduct,
it achieves a better bound on $|E_{\mathrm{adm}}|$.

######  Theorem 14.

For any sufficiently small $\varepsilon>0$, there exists a
$\text{poly}(n,\frac{1}{\varepsilon})$-time algorithm that, given a
Correlation Clustering instance $(V,E^{+}\uplus E^{-})$ with optimal value
${\mathrm{opt}}$ (which is not given to us), produces a preclustered instance
$({\mathcal{K}},E_{\mathrm{adm}})$ such that

  * •

there exists a good clustering w.r.t $({\mathcal{K}},E_{\mathrm{adm}})$, whose
cost is at most $(1+\varepsilon){\mathrm{opt}}$, and

  * •

$|E_{\mathrm{adm}}|\leq
O\big{(}\frac{1}{\varepsilon^{2}}\big{)}\cdot{\mathrm{opt}}$.

We can assume in the preclustered instance $({\mathcal{K}},E_{\mathrm{adm}})$,
the edges between two different atoms $K$ and $K^{\prime}$ are all admissible,
or all non-admissible. If one edge between them is non-admissible, we can
change all other edges to non-admissible edges. This will not change the set
of good clusterings, and it will decrease $|E_{\mathrm{adm}}|$.

We apply Theorem 14 to obtain a preclustered instance
$({\mathcal{K}},E_{\mathrm{adm}})$, with the unknown good clustering
${\mathcal{C}}^{*}_{1}$. We define $K_{u}$ to be the atom that contains $u$,
and $k_{u}=|K_{u}|$. We shall use $N_{\mathrm{adm}}(u)$ to be the set of
vertices $v$ such that $uv\in E_{\mathrm{adm}}$; so
$N_{\mathrm{adm}}(u)=N_{\mathrm{adm}}(v)$ if $v\in K_{u}$. We further process
the good clustering ${\mathcal{C}}^{*}_{1}$ using the following procedure in
[CLLN23]. This procedure is not a part of our algorithm; it is only for
analysis purpose.

1:while there exists some $K_{u}$ in a cluster $C\in{\mathcal{C}}^{*}_{1}$
with $k_{u}<|C|\leq k_{u}+\varepsilon_{1}\cdot|N_{\mathrm{adm}}(u)|$ do

2:
${\mathcal{C}}^{*}_{1}\leftarrow{\mathcal{C}}^{*}_{1}\setminus\\{C\\}\cup\\{K_{u},C\setminus
K_{u}\\}$

######  Claim 15.

The procedure increases $\mathrm{obj}({\mathcal{C}}^{*}_{1})$ by at most
$2\varepsilon_{1}\cdot|E_{\mathrm{adm}}|$.

###### Proof.

Whenever we break $C$ into $K_{u}$ and $C\setminus K_{u}$ in the procedure,
the cost increase is at most $k_{u}\cdot(|C|-k_{u})\leq
k_{u}\cdot\varepsilon_{1}\cdot|N_{\mathrm{adm}}(u)|=\varepsilon_{1}\sum_{v\in
K_{u}}|N_{\mathrm{adm}}(v)|$. We separate each atom $K_{u}$ at most once.
Therefore, the total cost increase is at most $\varepsilon_{1}\sum_{v\in
V}|N_{\mathrm{adm}}(v)|=2\varepsilon_{1}\cdot|E_{\mathrm{adm}}|$. ∎

So, the cost of ${\mathcal{C}}^{*}_{1}$ after the procedure will be at most
$(1+\varepsilon){\mathrm{opt}}+O(\varepsilon_{1})|E_{\mathrm{adm}}|$.
Crucially, the following property is satisfied:

  1. (A1)

For every $u\in V$, $K_{u}$ is either a cluster in ${\mathcal{C}}^{*}_{1}$, or
in a cluster of size more than
$k_{u}+\varepsilon_{1}\cdot|N_{\mathrm{adm}}(u)|$.

###  4.2 Bounded Sub-Cluster LP Relaxation for Preclustered Instances

Following [CLLN23], we form an LP relaxation aiming at finding the good
clustering ${\mathcal{C}}^{*}_{1}$. In the LP, we have a variable $y^{s}_{S}$,
for every $s\in[n]$, and $S\subseteq V$ of size at most $r$ (recall that
$r=\Theta(1/\varepsilon^{12})$), that denotes the number of clusters in
${\mathcal{C}}^{*}_{1}$ of size $s$ containing $S$ as a subset. When
$S\neq\emptyset$, there is at most one such cluster and thus
$y^{s}_{S}\in\\{0,1\\}$ indicates if $S$ is a subset of a cluster of size $s$
in ${\mathcal{C}}^{*}_{1}$. For every $S\subseteq V$ of size at most $r$, let
$y_{S}:=\sum_{s}y^{s}_{S}$ denote the number of clusters (of any size) in
${\mathcal{C}}^{*}_{1}$ containing $S$ as a subset. Again, if
$S\neq\emptyset$, then $y_{S}\in\\{0,1\\}$ indicates if $S$ is a subset of a
cluster in ${\mathcal{C}}^{*}_{1}$. For every $uv\in{V\choose 2}$, we have a
variable $x_{uv}$ indicating if $u$ and $v$ are separated or not in
${\mathcal{C}}^{*}_{1}$. We call the LP the _bounded sub-cluster LP
relaxation_ , as we have variables indicating if a small set $S$ is a subset
of a cluster or not.

We use the following type of shorthand: $y^{s}_{u}$ for $y^{s}_{\\{u\\}}$,
$y^{s}_{uv}$ for $y^{s}_{\\{u,v\\}}$, and $y^{s}_{Su}$ for
$y^{s}_{S\cup\\{u\\}}$. The bounded sub-cluster LP is defined as follows. In
the description, we always have $s\in[n],u\in V$ and $uv\in{V\choose 2}$. For
convenience, we omit the restrictions. By default, any variable of the form
$y_{S}$ or $y^{s}_{S}$ has $|S|\leq r$; if not, we do not have the variable
and the constraint involving it.

$\min\qquad\mathrm{obj}(x)$ (bounded sub-cluster LP)

$\displaystyle\sum_{s=1}^{n}y^{s}_{S}$ $\displaystyle=y_{S}$
$\displaystyle\forall S$ (6) $\displaystyle y_{u}$ $\displaystyle=1$
$\displaystyle\forall u$ (7) $\displaystyle y_{uv}+x_{uv}$ $\displaystyle=1$
$\displaystyle\forall uv$ (8) $\displaystyle\frac{1}{s}\sum_{u}y^{s}_{Su}$
$\displaystyle=y^{s}_{S}$ $\displaystyle\forall s,S$ (9) $\displaystyle
y^{s}_{S}$ $\displaystyle\geq 0$ $\displaystyle\forall s,S$ (10)

$\displaystyle x_{uv}$ $\displaystyle=0$ $\displaystyle\forall u,v\text{ in a
same }K\in{\mathcal{K}}$ (11) $\displaystyle x_{uv}$ $\displaystyle=1$
$\displaystyle\forall\text{non-admissible edge }uv$ (12) $\displaystyle
y^{s}_{u}$ $\displaystyle=0$ $\displaystyle\forall
u,s\in[k_{u}-1]\cup\big{[}k_{u}+1,k_{u}+\varepsilon_{1}|N_{\mathrm{adm}}(u)|\big{]}$
(13) $\displaystyle\sum_{T^{\prime}\subseteq T}(-1)^{|T^{\prime}|}y^{s}_{S\cup
T^{\prime}}$ $\displaystyle\in[0,y^{s}_{S}]$ $\displaystyle\forall s,S\cap
T=\emptyset$ (14)

(6) gives the definition of $y_{S}$, (7) requires $u$ to be contained in some
cluster, and (8) gives the definition of $x_{uv}$. (9) says if $y^{s}_{S}=1$,
then there are exactly $s$ elements $u\in V$ with $y^{s}_{Su}=1$. (An
exception is when $S=\emptyset$; but the equality also holds.) (10) is the
non-negativity constraint. (11) and (12) follows from that
${\mathcal{C}}^{*}_{1}$ is a good clustering, and (13) follows from (A1). The
left side of (14) is the number of clusters of size $s$ containing $S$ but
does not contain any vertex in $T$. So the inequality holds. This corresponds
to a Sherali-Adams relaxation needed for the correlated rounding [RT12], see
Lemma 16. The running time for solving the LP is
$n^{O(r)}=n^{O(1/\varepsilon^{12})}$.

###  4.3 Sampling One Cluster Using LP Solution to the Bounded Sub-Cluster LP

We solve the bounded sub-cluster LP to obtain the $y$ and $x$ vectors. Given
$y$, we can use the procedure construct-cluster described in Algorithm 3,
which is from [CLLN23], to produce a random cluster $C$.

Algorithm 3 construct-cluster$(y)$

1:randomly choose a cardinality $s$, so that $s$ is chosen with probability
$\frac{y^{s}_{\emptyset}}{y_{\emptyset}}$

2:randomly choose a vertex $u\in V$, so that $u$ is chosen with probability
$\frac{y^{s}_{u}}{sy^{s}_{\emptyset}}$

3:define a vector $y^{\prime}$ such that
$y^{\prime}_{S}=\frac{y^{s}_{Su}}{y^{s}_{u}}$ for every $S\subseteq V$ of size
at most $r-1$

4:apply the Raghavendra-Tan correlated rounding technique over the fractional
set $y^{\prime}$ to construct a cluster $C\subseteq V$ that does not break any
atom, and return $C$

With (14), the Raghavendra-Tan technique can be applied:

######  Lemma 16 ([RT12]).

In Step 4 of Algorithm 3, one can sample a set $C\subseteq V$ that does not
break atoms in time $n^{O(r)}$ such that

  * •

For each $v\in V$, $\Pr[v\in C]=y^{\prime}_{v}$.

  * •

$\frac{1}{|N_{\mathrm{adm}}(u)|^{2}}\sum_{v,w\in
N_{\mathrm{adm}}(u)}\big{|}\Pr[v,w\in
C]-y^{\prime}_{vw}\big{|}\leq\varepsilon_{\mathrm{rt}}$.

Recall that $\varepsilon_{\mathrm{rt}}=\Theta(1/\sqrt{r})$ and the hidden
constant inside $\Theta(\cdot)$ is large enough.

As in [CLLN23], we define $\mathrm{err}^{s}_{vw|u}$ to be the error generated
by the procedure when we choose $s$ as the cardinality and $u$ as the pivot:

$\displaystyle\mathrm{err}^{s}_{vw|u}:=\left|\Pr\big{[}v,w\in
C|s,u\big{]}-\frac{y^{s}_{uvw}}{y^{s}_{u}}\right|,\forall vw\in{V\choose 2},$

and

$\displaystyle\mathrm{err}^{s}_{vw}:=\frac{1}{sy^{s}_{\emptyset}}\sum_{u\in
V}y^{s}_{u}\cdot\mathrm{err}^{s}_{vw|u}\text{ and
}\mathrm{err}_{vw}:=\sum_{s}\frac{y^{s}_{\emptyset}}{y_{\emptyset}}\cdot\mathrm{err}^{s}_{vw}$

as the error for $vw$ conditioned on $s$, and the unconditioned error. Notice
that all these quantities are expectations of random variables, and thus
deterministic.

The following two lemmas can be proved using the same arguments as in
[CLLN23].

######  Lemma 17 ([CLLN23]).

For any $v\in V$, we have $\Pr[v\in C]=\frac{1}{y_{\emptyset}}$.

######  Lemma 18 ([CLLN23]).

Focus on an edge $vw\in{V\choose 2}$.

  1. 1.

$\Pr\left[v\in C,w\notin C\right]\leq\frac{1}{y_{\emptyset}}\cdot
x_{vw}+\mathrm{err}_{vw}$.

  2. 2.

$\Pr\left[|\\{v,w\\}\subseteq C\right]\leq\frac{1}{y_{\emptyset}}\cdot
y_{vw}+\mathrm{err}_{vw}$.

A similar lemma to the following is proved in [CLLN23]. The parameters we use
here are slightly different and we provide a proof for completeness.

######  Lemma 19.

$\displaystyle\sum_{vw\in{V\choose 2}}\mathrm{err}_{vw}\leq
O(\varepsilon_{1})\cdot\frac{1}{y_{\emptyset}}|E_{\mathrm{adm}}|$.

###### Proof.

Throughout the proof, we assume $u,v,w$ are all in $V$, $vw$ and $uw$ are in
$V\choose 2$.

Fix some $s\in[n],u\in V$ with $y^{s}_{u}>0$, and we now bound
$\sum_{vw}\mathrm{err}^{s}_{vw|u}$. If $s=k_{u}$, then $C=K_{u}$; no errors
will be created and the quantity is $0$. Assume $s>k_{u}$. By (13), we have
that $s>k_{u}+\varepsilon_{1}\cdot|N_{\mathrm{adm}}(u)|$, since otherwise we
shall $y^{s}_{u}=0$. By the second property of Lemma 16, we have
$\sum_{vw}\mathrm{err}^{s}_{vw|u}\leq\frac{\varepsilon_{\mathrm{rt}}}{2}|N_{\mathrm{adm}}(u)|^{2}$.
(Notice that if one of $v$ and $w$ is not in $N_{\mathrm{adm}}(u)$, then
$\mathrm{err}^{s}_{vw|u}=0$.) Recall that
$\varepsilon_{\mathrm{rt}}=\varepsilon_{1}^{2}$. Therefore,

$\displaystyle\sum_{vw\in{V\choose 2}}\mathrm{err}^{s}_{vw|u}$
$\displaystyle\leq\frac{\varepsilon_{\mathrm{rt}}}{2}\cdot|N_{\mathrm{adm}}(u)|^{2}\leq\frac{\varepsilon_{\mathrm{rt}}}{2\varepsilon_{1}}\cdot|N_{\mathrm{adm}}(u)|\cdot(s-k_{u})$
$\displaystyle=\frac{\varepsilon_{1}}{2}\cdot|N_{\mathrm{adm}}(u)|\cdot\sum_{v\in
N_{\mathrm{adm}}(u)}\frac{y^{s}_{uv}}{y^{s}_{u}}=\frac{\varepsilon_{1}}{2}\cdot\sum_{v,w\in
N_{\mathrm{adm}}(u)}\frac{y^{s}_{uv}}{y^{s}_{u}}.$

The first equality is by (9) and $y^{s}_{uv}=y^{s}_{u}$ for every $v\in
K_{u}$. (To see this, notice that $y^{s}_{uv}\leq y^{s}_{u}$ is implied by
(14). We have $y_{uv}=\sum_{s}y^{s}_{uv}$, $y_{u}=\sum_{s}y^{s}_{u}$, and
$y_{uv}=y_{u}=1$ if $v\in K_{u}$.)

Considering the inequalities over all $u\in V$, we have

$\displaystyle\sum_{vw}\mathrm{err}^{s}_{vw}$
$\displaystyle=\frac{1}{sy^{s}_{\emptyset}}\sum_{u}y^{s}_{u}\cdot\sum_{vw}\mathrm{err}^{s}_{vw|u}\leq\frac{1}{sy^{s}_{\emptyset}}\sum_{u}y^{s}_{u}\cdot\sum_{v,w\in
N_{\mathrm{adm}}(u)}\frac{\varepsilon_{1}}{2}\cdot\frac{y^{s}_{uv}}{y^{s}_{u}}=\frac{\varepsilon_{1}}{2}\cdot\frac{1}{sy^{s}_{\emptyset}}\cdot\sum_{u\in
V,v,w\in N_{\mathrm{adm}}(u)}y^{s}_{uv}$
$\displaystyle=\frac{\varepsilon_{1}}{2}\cdot\sum_{v\in
V}\frac{y^{s}_{v}}{sy^{s}_{\emptyset}}\sum_{u\in N_{\mathrm{adm}}(v),w\in
N_{\mathrm{adm}}(u)}\frac{y^{s}_{uv}}{y^{s}_{v}}\quad\leq\quad\frac{\varepsilon_{1}}{2}\cdot\sum_{v\in
V}\frac{y^{s}_{v}}{sy^{s}_{\emptyset}}\sum_{uw\in
E_{\mathrm{adm}}}\left(\frac{y^{s}_{uv}+y^{s}_{vw}}{y^{s}_{v}}\right)$
$\displaystyle\leq\varepsilon_{1}\cdot\sum_{v\in
V}\frac{y^{s}_{v}}{sy^{s}_{\emptyset}}\sum_{uw\in
E_{\mathrm{adm}}}\Pr[C\cap\\{u,w\\}\neq\emptyset\mid s,v\text{ is pivot}]$
$\displaystyle=\varepsilon_{1}\sum_{uw\in
E_{\mathrm{adm}}}\Pr[C\cap\\{u,w\\}\neq\emptyset\mid s].$

To see the last inequality, notice that $\frac{y^{s}_{uv}}{y^{s}_{v}}=\Pr[u\in
C|s,v\text{ is pivot}]\leq\Pr[C\cap\\{u,w\\}\neq\emptyset|s,v\text{ is
pivot}]$. The same inequality holds for $\frac{y^{s}_{vw}}{y^{s}_{v}}$.

Finally, we take all $s$ into consideration:

$\displaystyle\sum_{vw}\mathrm{err}_{vw}$
$\displaystyle=\sum_{s}\frac{y^{s}_{\emptyset}}{y_{\emptyset}}\cdot\sum_{vw}\mathrm{err}^{s}_{vw}\leq\varepsilon_{1}\cdot\sum_{s}\frac{y^{s}_{\emptyset}}{y_{\emptyset}}\sum_{uw\in
E_{\mathrm{adm}}}\Pr[C\cap\\{u,w\\}\neq\emptyset|s]$
$\displaystyle=\varepsilon_{1}\cdot\sum_{uw\in
E_{\mathrm{adm}}}\Pr[C\cap\\{u,w\\}\neq\emptyset]\leq\frac{2\varepsilon_{1}}{y_{\emptyset}}|E_{\mathrm{adm}}|+3\varepsilon_{1}\sum_{uw\in{V\choose
2}}\mathrm{err}_{uw}.$

To see the last inequality, we notice that $C\cap\\{u,w\\}\neq\emptyset$ is
the union of the 3 disjoint events: $u\in C$ and $w\notin C$, $u\notin C$ and
$w\in C$, and $\\{u,w\\}\notin C$. By Lemma 18, we have
$\Pr[C\cap\\{u,w\\}\neq\emptyset]\leq\frac{2x_{vw}+y_{vw}}{y_{\emptyset}}+3\cdot\mathrm{err}_{uw}\leq\frac{2}{y_{\emptyset}}+3\cdot\mathrm{err}_{uw}$.
So, we have
$\sum_{vw}\mathrm{err}_{vw}\leq\frac{1}{1-3\varepsilon_{1}}\cdot\frac{2\varepsilon_{1}}{y_{\emptyset}}|E_{\mathrm{adm}}|$.
This proves the lemma. ∎

###  4.4 Construction of Solution to the Cluster LP Using Independently
Sampled Clusters

With all the ingredients, we can now describe our algorithm for solving the
cluster LP approximately, finishing the proof of Theorem 1. Let
$\Delta=\Theta\left(\frac{n^{2}\log
n}{\varepsilon_{1}^{2}|E_{\mathrm{adm}}|}\right)$ with a large enough hidden
constant, and $\Delta y_{\emptyset}$ being an integer. (We assume
$|E_{\mathrm{adm}}|\geq 1$ since otherwise the preclustered instance is
trivial.) We run Algorithm 3 $\Delta y_{\emptyset}$ times independently to
obtain clusters $C_{1},C_{2},\cdots,C_{\Delta y_{\emptyset}}$.

We use the following variant of Chernoff bound.

######  Theorem 20.

Let $X_{1},X_{2},X_{3},\cdots,X_{n}$ be independent (not necessarily iid)
random varibles which take values in $[0,1]$. Let
$X=\sum_{i=1}^{n}X_{i},\mu=\operatorname*{{\mathbb{E}}}[X]$, and
$\mu^{\prime}\geq\mu$ be a real. Then for any $\delta\in(0,1)$, we have

$\displaystyle\Pr[X<(1-\delta)\mu]<e^{-\delta^{2}\mu/2}\qquad\text{and}\qquad\Pr[X>\mu+\delta\mu^{\prime}]<e^{-\delta^{2}\mu^{\prime}/3}.$

For every $u\in V$, let $R_{u}=\\{t:u\in C_{t}\\}$. Notice that $\Delta
y_{\emptyset}\cdot\frac{|E_{\mathrm{adm}}|}{y_{\emptyset}n^{2}}=\Theta\big{(}\frac{\log
n}{\varepsilon_{1}^{2}}\big{)}$, with a large enough hidden constant. Using
Chernoff bound and union bound, we can prove that with probability at least
$1-1/n$, the following conditions hold.

  * •

For every $u\in V$, we have $|R_{u}|\geq(1-\varepsilon_{1})\Delta
y_{\emptyset}\cdot\frac{1}{y_{\emptyset}}=(1-\varepsilon_{1})\Delta$.

  * •

For every $u,v\in V$ such that $uv\in E^{+}$, we have

$\displaystyle|R_{u}\setminus R_{v}|$ $\displaystyle\leq\Delta
y_{\emptyset}\left(\frac{x_{uv}}{y_{\emptyset}}+\mathrm{err}_{uv}+\varepsilon_{1}\cdot\max\left\\{\frac{x_{uv}}{y_{\emptyset}}+\mathrm{err}_{uv},\frac{|E_{\mathrm{adm}}|}{y_{\emptyset}n^{2}}\right\\}\right)$
$\displaystyle\leq(1+\varepsilon_{1})\Delta(x_{uv}+y_{\emptyset}\mathrm{err}_{uv})+\frac{\varepsilon_{1}\Delta|E_{\mathrm{adm}}|}{n^{2}}.$
(15)

  * •

For every $uv\in E^{-}$, we have

$\displaystyle|R_{u}\cap R_{v}|$ $\displaystyle\leq\Delta
y_{\emptyset}\left(\frac{y_{uv}}{y_{\emptyset}}+\mathrm{err}_{uv}+\varepsilon_{1}\cdot\max\left\\{\frac{y_{uv}}{y_{\emptyset}}+\mathrm{err}_{uv},\frac{|E_{\mathrm{adm}}|}{y_{\emptyset}n^{2}}\right\\}\right)$
$\displaystyle\leq(1+\varepsilon_{1})\Delta(y_{uv}+y_{\emptyset}\mathrm{err}_{uv})+\frac{\varepsilon_{1}\Delta|E_{\mathrm{adm}}|}{n^{2}}.$

From now on we assume the conditions hold. For every $u\in V$, we let
$R^{\prime}_{u}$ be the set of the
${\left\lceil(1-\varepsilon)\Delta\right\rceil}$ smallest indices in $R_{u}$.
Clearly, $|R^{\prime}_{u}\cap R^{\prime}_{v}|\leq|R_{u}\cap R_{v}|$. We show
$|R^{\prime}_{u}\setminus R^{\prime}_{v}|$ is still upper bounded by (15).

######  Claim 21.

For every $uv\in E^{+}$ we have $\max\\{|R^{\prime}_{u}\setminus
R^{\prime}_{v}|,|R^{\prime}_{v}\setminus
R^{\prime}_{u}|\\}\leq(1+\varepsilon_{1})\Delta(x_{uv}+y_{\emptyset}\mathrm{err}_{uv})+\frac{\varepsilon_{1}\Delta|E_{\mathrm{adm}}|}{n^{2}}$.

###### Proof.

For convenience, we use $B$ to denote the upper bound
$(1+\varepsilon_{1})\Delta(x_{uv}+y_{\emptyset}\mathrm{err}_{uv})+\frac{\varepsilon_{1}\Delta|E_{\mathrm{adm}}|}{n^{2}}$.
We think of $R^{\prime}_{u}$ ($R^{\prime}_{v}$ resp.) as obtained from the set
$R_{u}$ ($R_{v}$ resp.) by removing the largest indices one by one. Wlog we
assume $|R_{u}|\geq|R_{v}|$; and thus initially $|R_{v}\setminus
R_{u}|\leq|R_{u}\setminus R_{v}|\leq B$. We remove the elements from $R_{u}$
and $R_{v}$ in two stages.

In the first stage we do the following. While $|R_{u}|>|R_{v}|$, we remove the
largest index from $R_{u}$. This can not increase $|R_{u}\setminus R_{v}|$.
After the first stage, we have $|R_{u}\setminus R_{v}|=|R_{v}\setminus
R_{u}|\leq B$.

In the second stage we do the following. While
$|R_{u}|=|R_{v}|>{\left\lceil(1-\varepsilon)\Delta\right\rceil}$, we remove
the largest index in $R_{u}$ from $R_{u}$, and do the same for $R_{v}$.
Consider one iteration of the while loop. If the two indices are the same,
then $|R_{u}\setminus R_{v}|=|R_{v}\setminus R_{u}|$ does not change.
Otherwise, wlog we assume the index we removed from $R_{u}$ is larger. Then
removing the index in $R_{u}$ will decrease $|R_{u}\setminus R_{v}|$. So the
iteration can not increase $|R_{u}\setminus R_{v}|=|R_{v}\setminus R_{u}|$. ∎

Then, for every $t\in[1,\Delta y_{\emptyset}]$, we define
$C^{\prime}_{t}=\\{u:t\in R^{\prime}_{u}\\}\subseteq C_{t}$; then every $v$ is
contained in $C^{\prime}_{t}$ for exactly
${\left\lceil(1-\varepsilon)\Delta\right\rceil}$ values of $t$. We define
$z_{S}=\frac{1}{{\left\lceil(1-\varepsilon)\Delta\right\rceil}}\cdot|\\{t:C^{\prime}_{t}=S\\}|$
for every $S\subseteq V$ with $S\neq\emptyset$. Define
$\tilde{x}_{uv}=1-\sum_{\\{u,v\\}\subseteq S}z_{S}$ for every $uv\in{V\choose
2}$. Then $(\tilde{x},z)$ is a valid solution to the cluster LP.

For a $uv\in E^{+}$, we have

$\displaystyle\tilde{x}_{uv}=\frac{1}{{\left\lceil(1-\varepsilon)\Delta\right\rceil}}\cdot|R^{\prime}_{u}\setminus
R^{\prime}_{v}|\leq\frac{1+\varepsilon_{1}}{1-\varepsilon}(x_{uv}+y_{\emptyset}\mathrm{err}_{uv})+\frac{\varepsilon_{1}|E_{\mathrm{adm}}|}{(1-\varepsilon)n^{2}}.$

For a $uv\in E^{-}$, we have

$\displaystyle(1-\tilde{x}_{uv})=\frac{1}{{\left\lceil(1-\varepsilon)\Delta\right\rceil}}\cdot|R^{\prime}_{u}\cap
R^{\prime}_{v}|\leq\frac{1+\varepsilon_{1}}{1-\varepsilon}(1-x_{uv}+y_{\emptyset}\mathrm{err}_{uv})+\frac{\varepsilon_{1}|E_{\mathrm{adm}}|}{(1-\varepsilon)n^{2}}.$

Therefore,

$\displaystyle\mathrm{obj}(\tilde{x})$
$\displaystyle\leq(1+O(\varepsilon))\left(\mathrm{obj}(x)+y_{\emptyset}\sum_{uv\in{V\choose
2}}\mathrm{err}_{uv}\right)+O(\varepsilon_{1})|E_{\mathrm{adm}}|\leq(1+O(\varepsilon))\mathrm{obj}(x)+O(\varepsilon_{1})|E_{\mathrm{adm}}|$
$\displaystyle\leq(1+O(\varepsilon))\cdot{\mathrm{opt}}+O(\varepsilon^{3})\cdot
O\big{(}\frac{1}{\varepsilon^{2}}\big{)}\cdot{\mathrm{opt}}=(1+O(\varepsilon)){\mathrm{opt}}.$

The second inequality is due to Lemma 19, and the third one used that
$|E_{\mathrm{adm}}|\leq
O\big{(}\frac{1}{\varepsilon^{2}}\big{)}\cdot{\mathrm{opt}}$. By scaling
$\varepsilon$, the upper bound can be made to $(1+\varepsilon){\mathrm{opt}}$.
This finishes the proof of Theorem 1.

##  5 Triangle Analysis used in 1.5-Approximation: Proof of Lemma 9

The goal of this section is to prove Lemma 9, which is restated here. See 9
The proof of Lemma 9 follows from Lemma 25, 26, 27, 28, 29 which we prove in
this section. First, we recall some notation.

#### Notations and Useful Observations

We define some notation and make some observations that will be useful in this
section and in Sections 6 and 7. Recall that we are given a polynomial-sized
LP solution $(z=(z_{S})_{S\subseteq V},x\in[0,1]^{V\choose 2})$ to (cluster
LP). For a $+$edge $uv$, we say $uv$ is _short_ if $x_{uv}\leq\frac{1}{3}$ and
_long_ if $x_{uv}>\frac{1}{3}$. Notice that the pivot-based rounding procedure
(Algorithm 1) treat short and long $+$edges differently. For vertices
$u,v,w\in V$, we define

$\displaystyle y_{uv}$
$\displaystyle:=\sum_{S\supseteq\\{u,v\\}}z_{S}\in[0,1],\qquad
y_{uvw}:=\sum_{S\supseteq\\{u,v,w\\}}z_{S}\in[0,1],\qquad
y_{uv|w}:=y_{uv}-y_{uvw}\in[0,1],$ $\displaystyle y_{u|v|w}$
$\displaystyle:=1-y_{uv|w}-y_{uw|v}-y_{vw|u}-y_{uvw}=1-y_{uv}-y_{uw}-y_{vw}+2y_{uvw}\in[0,1].$

To see that $y_{u|v|w}\in[0,1]$, notice that
$y_{uv}+y_{uw}+y_{vw}-2y_{uvw}=\sum_{S}z_{S}\cdot(1_{\\{u,v\\}\subseteq
S}+1_{\\{u,w\\}\subseteq S}+1_{\\{v,w\\}\subseteq S}-2\cdot
1_{\\{u,v,w\\}\subseteq S})$. The quantity after $z_{S}$ is either $0$ or $1$,
depending on the size of $S\cap\\{u,v,w\\}$. In an integral solution $z$,
$y_{uv},y_{uvw},y_{uv|w}$ and $y_{u|v|w}$, respectively, indicate if $u$ and
$v$ are in the same cluster, if $u,v$ and $w$ are all in the same cluster, if
$u$ and $v$ are in the same cluster not containing $w$, and if $u,v,w$ are in
three different clusters. These definitions also hold when $u,v$ and $w$ are
not distinct vertices.

In the following two claims, we focus on one iteration of the while loop in
Algorithm 2. $V^{\prime}$ is the vertex set at the beginning of the iteration,
and $C$ is the cluster obtained at the end. We use $u$ to denote the event
that $u$ is the chosen pivot.

######  Claim 22.

Let $u,v\in V^{\prime}$ (it is possible that $u=v$). Then

$\displaystyle\Pr[v\in C\mid u]=\begin{cases}1&\text{if $uv$ is a short
$+$edge}\\\ 1-x_{uv}=y_{uv}&\text{otherwise}\end{cases}.$

######  Claim 23.

Let $u,v,w\in V^{\prime}$ with $v\neq w$. Then

$\displaystyle\Pr[\\{v,w\\}\subseteq C\mid u]$
$\displaystyle=\begin{cases}y_{uvw}&\text{if both $uv$ and $uw$ are long
$+$edges}\\\ \Pr[v\in C\mid u]\cdot\Pr[w\in C\mid
u]&\text{otherwise}\end{cases},$ $\displaystyle\Pr[v\in C\wedge w\notin C\mid
u]$ $\displaystyle=\begin{cases}y_{uv|w}&\text{if both $uv$ and $uw$ are long
$+$edges}\\\ \Pr[v\in C\mid u]\cdot\big{(}1-\Pr[w\in C\mid
u]\big{)}&\text{otherwise}\end{cases}.$

We now prove some useful facts about the budget functions defined in Section
2,

$\displaystyle
b^{+}_{\alpha}(x)=\frac{\alpha}{1-\alpha/2}\cdot\frac{x^{2}}{1+x},\qquad\text{and}\qquad
b^{-}_{\alpha}(x)=\frac{\alpha}{1-\alpha/2}\cdot\frac{(1+2x)(1-x)}{2(1+x)},\qquad\forall
x\in[0,1].$

######  Lemma 24.

For any $\alpha\in[1,2)$, $b^{+}_{\alpha}(x)$ is convex and decreasing.
Moreover, $b^{-}_{\alpha}(x)$ is increasing.

###### Proof.

Consider the first and second derivative of $b^{+}_{\alpha}(x)$,

$\displaystyle\frac{d}{dx}b^{+}_{\alpha}(x)=\frac{\alpha}{1-\alpha/2}\cdot\frac{x(2+x)}{(1+x)^{2}}\geq
0,$
$\displaystyle\frac{d^{2}}{d^{2}x}b^{+}_{\alpha}(x)=\frac{\alpha}{1-\alpha/2}\cdot\frac{2}{(x+1)^{3}}\geq
0.$

Here, we used that $\frac{\alpha}{1-\alpha/2}\geq 0$ and $x\geq 0$. Similar,
for $b^{-}_{\alpha}(x)$,

$\displaystyle\frac{d}{dx}b^{-}_{\alpha}(x)=\frac{\alpha}{1-\alpha/2}\cdot\frac{-x(x+2)}{(1+x)^{2}}\leq
0.$

Now we start the proof of Lemma 9. Note that for $\alpha=1.5$, the budget
functions simplify to

$\displaystyle b^{+}(x):=\frac{6x^{2}}{1+x},\qquad\text{and}\qquad
b^{-}(x):=\frac{3(1+2x)(1-x)}{(1+x)},\qquad\forall x\in[0,1].$

We will prove the lemma by considering each possible triangle type separately.
That is, degenerate triangles, triangles with no $+$edge ($-\\!-\\!-$
triangles), triangles with one $+$edge ($+\\!-\\!-$ triangles), triangles with
two $+$edges ($+\\!+\\!-$ triangles) and lastly, triangles with three $+$edges
($+\\!+\\!+$ triangles). Moreover, recall that the pivot rounding algorithm
treats short $+$edges differently than long $+$edges. Therefore, for each type
of triangle, we consider different cases that specify how many short and long
$+$edges the triangle contains.

#### Degenerate triangles

For the case when two of the vertices $u,v,w$ are identical, we want to make
sure that $\mathrm{cost}(u,v)\leq\Delta(u,v)$.

######  Lemma 25.

Fix budget functions $b^{+}\equiv b^{+}_{\alpha}$ and $b^{-}\equiv
b^{-}_{\alpha}$, where $\alpha\geq 4/3$. For any degenerate triangle $T$, we
have $\mathrm{cost}(T)\leq\Delta(T)$.

###### Proof.

For a $-$edge with value $x$ this is equivalent to

$\displaystyle(1-x)\leq\frac{\alpha(1+2x)(1-x)}{(2-\alpha)(1+x)}.$

This holds true since
$\frac{\alpha(1+2x)}{(2-\alpha)(1+x)}\geq\frac{\alpha}{(2-\alpha)}\geq 1$, for
any $\alpha\geq 1$. For short $+$edges the cost is 0 and the inequality holds
trivially. For long $+$edges with value $x>\frac{1}{3}$ we need,

$\displaystyle x\leq\frac{2\alpha x^{2}}{(2-\alpha)(1+x)}.$

This holds true since $\frac{2\alpha
x^{2}}{(2-\alpha)(1+x)}\geq\frac{2\alpha/3}{(2-\alpha)(1+1/3)}\geq 1$ for any
$\alpha\geq 4/3$. ∎

###  5.1 $+\\!+\\!+$ Triangles

######  Lemma 26.

Fix the budget function $b^{+}\equiv b^{+}_{\alpha}$, where $\alpha=1.5$. For
any $+\\!+\\!+$ triangle $T$, we have $\mathrm{cost}(T)\leq\Delta(T)$.

###### Proof.

We distinguish between the following cases: the triangle has three short
edges, two short edges, one short edge or no short edge.

#### (s,s,s)

$\mathrm{cost}(T)=0$ and $\Delta(T)\geq 0$.

#### (s,s,l)

For a $+\\!+\\!+$ triangle $T=(u,v,w)$, assume that $uv$ is long and $uw$,
$vw$ are short:

$\displaystyle\mathrm{cost}(T)$ $\displaystyle=2\cdot x_{uv},$
$\displaystyle\Delta(T)$
$\displaystyle=b^{+}(x_{uv})+b^{+}(x_{uw})+b^{+}(x_{vw})\geq
b^{+}(x_{uv})+2\cdot b^{+}\left(\frac{x_{uw}+x_{vw}}{2}\right)\geq
b^{+}(x_{uv})+2\cdot b^{+}\left({\frac{x_{uv}}{2}}\right).$

Here, we used that the function $b^{+}$ is convex (Lemma 24) together with the
triangle inequality, $x_{uv}\leq x_{uw}+x_{vw}$. For $x_{uv}>1/3$, we have
that

$\displaystyle\Delta(T)\geq b^{+}(x_{uv})+2\cdot
b^{+}\left({\frac{x_{uv}}{2}}\right)\geq\frac{3}{2}x_{uv}+\frac{7}{6}x_{uv}\geq
2\cdot x_{uv}=\mathrm{cost}(T).$

#### (s,l,l)

For a $+\\!+\\!+$ triangle $T=(u,v,w)$, assume that $uv$ is short and $uw$ and
$vw$ are long:

$\displaystyle\mathrm{cost}(T)$
$\displaystyle=x_{uw}+x_{vw}+y_{vw}+y_{uw}-2\cdot y_{uvw}$
$\displaystyle\Delta(T)$
$\displaystyle=b^{+}(x_{uw})+b^{+}(x_{vw})+b^{+}(x_{uv})\cdot(y_{vw}+y_{uw}-y_{uvw})$
$\displaystyle\geq b^{+}(x_{uw})+b^{+}(x_{vw}).$

Because $x_{uw}>1/3$,

$b^{+}(x_{uw})\geq\frac{3}{2}x_{uw}=\frac{3}{2}(1-y_{uw}).$

Hence,

$\displaystyle\Delta(T)-\mathrm{cost}(T)$
$\displaystyle\geq\frac{1}{2}(x_{uw}+x_{vw})-y_{vw}-y_{uw}+2\cdot y_{uvw}$
$\displaystyle=1-\frac{3}{2}(y_{vw}+y_{uw})+2\cdot y_{uvw}$ $\displaystyle\geq
y_{uv}+y_{vw}+y_{uw}-2\cdot y_{uvw}-\frac{3}{2}(y_{vw}+y_{uw})+2\cdot y_{uvw}$
$\displaystyle=y_{uv}-\frac{1}{2}(y_{vw}+y_{uw})$ $\displaystyle\geq 0.$

For the first inequality we used $1-(y_{uv}+y_{vw}+y_{uw}-2\cdot y_{uvw})\geq
0$ and for the second that $y_{vw},y_{uw}\leq\frac{2}{3}$ and
$y_{uv}\geq\frac{2}{3}$.

#### (l,l,l)

For a $+\\!+\\!+$ triangle $T$ where we use correlated rounding, [CLN22] show
that $\frac{\mathrm{cost}(T)}{\Delta(T)}\leq 1$, when we use budget
$\frac{3}{2}x$ for each $+$edge. We have $b^{+}(x)\geq\frac{3}{2}x$ for $x\geq
1/3$. ∎

###  5.2 $-\\!-\\!-$ Triangles

######  Lemma 27.

Fix the budget function $b^{-}\equiv b^{-}_{\alpha}$, where $\alpha\geq 1$.
For any $-\\!-\\!-$ triangle $T$, we have $\mathrm{cost}(T)\leq\Delta(T)$.

###### Proof.

We have that
$b^{-}_{\alpha}(x)=\frac{\alpha}{1-\alpha/2}\cdot\frac{(1+2x)(1-x)}{2(1+x)}\geq(1-x)$.
As before,
$\frac{\alpha(1+2x)}{(2-\alpha)(1+x)}\geq\frac{\alpha}{(2-\alpha)}\geq 1$, for
any $\alpha\geq 1$. [CLLN23] shows that the inequality holds true if the
coefficient is $1$.

$\displaystyle\mathrm{cost}(T)$
$\displaystyle=y_{uv}y_{uw}+y_{uv}y_{vw}+y_{uw}y_{vw}.$
$\displaystyle\Delta(T)$
$\displaystyle\geq(y_{uv}+y_{uw}-y_{uv}y_{uw})y_{vw}+(y_{uv}+y_{vw}-y_{uv}y_{vw})y_{uw}+(y_{uw}+y_{vw}-y_{uw}y_{vw})y_{uv}$
$\displaystyle=2(y_{uv}y_{uw}+y_{uv}y_{vw}+y_{uw}y_{vw})-3y_{uv}y_{uw}y_{vw}\geq
y_{uv}y_{uw}+y_{uv}y_{vw}+y_{uw}y_{vw}.$

∎

###  5.3 $+\\!-\\!-$ Triangles

######  Lemma 28.

Fix budget functions $b^{+}\equiv b^{+}_{\alpha}$ and $b^{-}\equiv
b^{-}_{\alpha}$, where $\alpha\geq\frac{4}{3}$. For any $+\\!-\\!-$ triangle
$T$, we have $\mathrm{cost}(T)\leq\Delta(T)$.

###### Proof.

We have to prove the following two cases.

#### short $+$edge

For a $+\\!-\\!-$ triangle $T=(u,v,w)$, assume that $uv$ is a short $+$edge
and $uw$ and $vw$ are $-$edges.

$\displaystyle
b^{-}_{\alpha}(x)=\frac{\alpha}{1-\alpha/2}\cdot\frac{(1+2x)(1-x)}{2(1+x)}\geq
2(1-x)$

Therefore, we have for $\mathrm{cost}(T)$ and $\Delta(T)$,

$\displaystyle\mathrm{cost}(T)$
$\displaystyle=y_{uw}+y_{vw}+y_{uw}+y_{vw}-2\cdot y_{uw}y_{vw}\leq
2(y_{uw}+y_{vw}),$ $\displaystyle\Delta(T)$ $\displaystyle\geq
b^{-}(x_{uw})+b^{-}(x_{vw})\geq 2(y_{uw}+y_{vw}).$

#### long $+$edge

For a $+\\!-\\!-$ triangle $T=(u,v,w)$, assume that $uv$ is a long $+$edge and
$uw$ and $vw$ are $-$edges. For $x\geq 1/3$, we can lower bound the budget of
the $+$edge,

$\displaystyle
b^{+}_{\alpha}(x)=\frac{\alpha}{1-\alpha/2}\cdot\frac{x^{2}}{1+x}\geq\frac{2\alpha/3}{(2-\alpha)(1+1/3)}x\geq
x.$

As above, $b^{-}(x)\geq 2(1-x)$. The inequality is true if the coefficient for
the $+$edge is $1$ and for the $-$edge is $2$, [CLLN23].

$\displaystyle\mathrm{cost}(T)$
$\displaystyle=y_{uw}y_{uv}+y_{vw}y_{uv}+y_{uw}+y_{vw}-2y_{uw}y_{vw}=(2-x_{uv})(y_{uw}+y_{vw})-2y_{uw}y_{vw}.$
$\displaystyle\Delta(T)$
$\displaystyle\geq(y_{uw}+y_{vw}-y_{uw}y_{vw})x_{uv}+2(y_{uw}+y_{uv}-y_{uw}y_{uv})y_{vw}+2(y_{vw}+y_{uv}-y_{vw}y_{uv})y_{uw}$
$\displaystyle=(y_{uw}+y_{vw}-y_{uw}y_{vw})x_{uv}+2(1-x_{uv}+y_{uw}x_{uv})y_{vw}+2(1-x_{uv}+y_{vw}x_{uv})y_{uw}$
$\displaystyle=(2-x_{uv})(y_{uw}+y_{vw})+3y_{uw}y_{vw}x_{uv}.$

∎

###  5.4 $+\\!+\\!-$ Triangles

######  Lemma 29.

Fix budget functions $b^{+}\equiv b^{+}_{\alpha}$ and $b^{-}\equiv
b^{-}_{\alpha}$, where $\alpha=\frac{3}{2}$. For any $+\\!-\\!-$ triangle $T$,
we have $\mathrm{cost}(T)\leq\Delta(T)$.

###### Proof.

Again, we distinguish cases depending on the number of short $+$edges.

#### (s,s)

For a $+\\!+\\!-$ triangle $T=(u,v,w)$, assume that $uv$ is a $-$edge and
$uw$, $vw$ are short $+$edges.

$\displaystyle\mathrm{cost}(T)$ $\displaystyle=2\cdot x_{uv}+1,$ (16)
$\displaystyle\Delta(T)$
$\displaystyle=b^{-}(x_{uv})+b^{+}(x_{uw})+b^{+}(x_{vw})\geq
b^{-}(x_{uv})+2\cdot b^{+}\left(\frac{x_{uw}+x_{vw}}{2}\right)\geq
b^{-}(x_{uv})+2\cdot b^{+}\left({\frac{x_{uv}}{2}}\right).$ (17)

As before, we used the convexity of $b^{+}$ (Lemma 24) together with the
triangle inequality, $x_{uv}\leq x_{uw}+x_{vw}$. The derivative of (17) w.r.t.
$x_{uv}$ is less than $0$ for $x_{uv}\geq 0$,

$-\frac{6x_{uv}(4+3x_{uv})}{(1+x_{uv})^{2}(2+x_{uv})^{2}}\leq 0.$

Hence, (17) is decreasing with $x_{uv}$. Observe that $x_{uv}\leq
x_{uw}+x_{vw}\leq\frac{2}{3}$. Since the cost is increasing with $x_{uv}$ we
only need to check the case $x_{uv}=\frac{2}{3}$,

$\displaystyle\Delta(T)-\mathrm{cost}(T)\geq
b^{-}\left(\frac{2}{3}\right)+2\cdot
b^{+}\left({\frac{1}{3}}\right)-\frac{7}{3}=\frac{1}{15}.$

#### (s,l)

For a $+\\!+\\!-$ triangle $T=(u,v,w)$, assume that $uv$ is a $-$edge, $uw$ is
a short $+$edge and $vw$ is a long $+$edge.

$\displaystyle\mathrm{cost}(T)$
$\displaystyle=x_{uv}+y_{vw}+y_{vw}+y_{uv}-2y_{vw}y_{uv}=1+2y_{wv}(1-y_{uv})=1+2(1-x_{wv})x_{uv},$
$\displaystyle\Delta(T)$
$\displaystyle=b^{+}(x_{vw})+b^{-}(x_{uv})+b^{+}(x_{uw})(y_{vw}+y_{uv}-y_{vw}y_{uv})$
$\displaystyle=b^{+}(x_{vw})+b^{-}(x_{uv})+b^{+}(x_{uw})(2-x_{vw}-x_{uv}-(1-x_{vw})(1-x_{uv})).$

#### Case 1

$x_{vw}\geq x_{uv}$.

$\displaystyle\Delta(T)$ $\displaystyle\geq b^{+}(x_{uv})+b^{-}(x_{uv})=3.$

$\mathrm{cost}(T)$ is always less than $3$.

#### Case 2

$x_{vw}\leq x_{uv}$. We have $x_{uw}\geq x_{uv}-x_{vw}$ by triangle
inequality. Since $b^{+}(x)$ is increasing by Lemma 24,

$\Delta(T)\geq
b^{+}(x_{vw})+b^{-}(x_{uv})+b^{+}(x_{uv}-x_{vw})(2-x_{vw}-x_{uv}-(1-x_{vw})(1-x_{uv})).$

For a fixed $z\coloneqq x_{uv}$, define $x\coloneqq x_{vw}\geq\frac{1}{3}$. We
need to argue that the difference

$\displaystyle\Delta(T)-\mathrm{cost}(T)=b^{+}(x)+b^{-}(z)+b^{+}(z-x)(2-x-z-(1-x)(1-z))-1-2(1-x)z$
(18)

is non-negative.

######  Claim 30.

(18) is increasing with $x$.

###### Proof..

The derivative of (18) w.r.t. $x$ is

$\displaystyle\frac{2(6x^{5}z+x^{4}(4-15z)z+4x^{3}z(-3-5z+3z^{2})+x^{2}z(-11+7z+22z^{2}-3z^{3}))}{(1+x)^{2}(1-x+z)^{2}}$
$\displaystyle+\frac{2(-z(5+z+2z^{2}+3z^{3})+x(12+6z+14z^{2}+8z^{3}-6z^{4}))}{(1+x)^{2}(1-x+z)^{2}},$
(19)

which is non-negative as long as the numerator is non-negative. The numerator
is a concave function in $x$. Indeed, the second derivative of the numerator
in (19) w.r.t. $x$ is

$\displaystyle
4z(-11+60x^{3}+x^{2}(24-90z)+7z+22z^{2}-3z^{3}+12x(-3-5z+3z^{2})).$ (20)

We want to show that (20) is non-positive. This is equivalent to

$\displaystyle-11+60x^{3}+x^{2}(24-90z)+7z+22z^{2}-3z^{3}+12x(-3-5z+3z^{2})\leq
0.$ (21)

Note that (21) is a convex function in $x$. Indeed, the second derivative
w.r.t. $x$ of (21) is equal to

$\displaystyle 12(4+30x-15z)\geq 0.$

The inequality holds true since either $z\geq 2/3$ and $x\geq z-\frac{1}{3}$
or $z\leq 2/3$. Hence, (21) is maximized for either $x=z$, $x=1/3$ or
$x=z-1/3$.

$\displaystyle x=z,$
$\displaystyle\quad\eqref{equ:1.5deriv4}=-11-29z-14z^{2}+3z^{3}\leq 0,$
$\displaystyle x=\frac{1}{3},$
$\displaystyle\quad\eqref{equ:1.5deriv4}=-\frac{163}{9}-23z+34z^{2}-3z^{3}\leq
0,$ $\displaystyle x=z-\frac{1}{3},$
$\displaystyle\quad\eqref{equ:1.5deriv4}=\frac{13}{9}-15z-26z^{2}+3z^{3}\leq
0.$

All inequalities above hold for $\frac{1}{3}\leq z\leq 1$. Thus, the numerator
of (19) is concave and minimized for either $x=1$, $x=1/3$ or $x=z-1/3$.

$\displaystyle x=z,$ $\displaystyle\quad 2z(7+5z+z^{2})\geq 0,$ $\displaystyle
x=\frac{1}{3},$
$\displaystyle\quad\frac{2}{27}(108-124z+95z^{2}+96z^{3}-144z^{4})\geq 0,$
$\displaystyle x=z-\frac{1}{3},$
$\displaystyle\quad-8+\frac{688}{81}z+\frac{86}{9}z^{2}+\frac{22}{3}z^{3}+\frac{14}{3}z^{4}\geq
0.$

The first two inequalities hold for $\frac{1}{3}\leq z\leq 1$. The last
inequality holds for $\frac{2}{3}\leq z\leq 1$. We can conclude that (18) is
indeed increasing with $x$. $\Diamond$

Therefore, we can assume that $x=1/3$ if $z\leq 2/3$ or $x=z-1/3$.

#### Case 2.1 $x=1/3.$

$\displaystyle\eqref{equ:1.5diff6}=\frac{1}{2}+b^{-}(z)+b^{+}\left(z-\frac{1}{3}\right)\left(1-\frac{1}{3}z\right)-1-\frac{4}{3}z.$
(22)

The derivative of (22) is equal to

$\displaystyle\frac{-2(-22+124z+494z^{2}+510z^{3}+153z^{4})}{3(1+z)^{2}(2+3z)^{2}}.$

For $z\geq x=1/3$, we have that,

$\displaystyle-22+124z+494z^{2}+510z^{3}+153z^{4}\geq 95.$

Hence, (22) is decreasing with $z$. For $z=2/3$, $\eqref{equ:1.5diff12}=2/5$.

#### Case 2.2 $x=z-1/3.$

$\displaystyle\eqref{equ:1.5diff6}=b^{+}\left(z-\frac{1}{3}\right)+b^{-}(z)+\frac{1}{2}\left(\frac{7}{3}-2z-\left(\frac{4}{3}-z\right)(1-z)\right)-1-2\left(\frac{4}{3}-z\right)z$
(23)

The derivative of (23) is equal to

$\displaystyle\frac{-80-148z-65z^{2}+72z^{3}+135z^{4}+54z^{5}}{2(1+z)^{2}(2+3z)^{2}}.$

For $0\leq z\leq 1$, we have that,

$\displaystyle-80-148z-65z^{2}+72z^{3}+135z^{4}+54z^{5}\leq 0.$

Hence, (23) is decreasing with $z$. For $z=1$,
$\eqref{equ:1.5diff8}=\frac{1}{10}$.

#### (l,l)

For a $+\\!+\\!-$ triangle $T=(u,v,w)$, assume that $uv$ is a $-$edge and
$uw$, $vw$ are long $+$edges. We will proceed similar to [CLLN23]. For
$-$edges we use a coefficient of $3$, $b^{-}(x)\geq 3(1-x)$. For $+$edges
define the coefficient $f(x)=\frac{6x}{1+x}$, $b^{+}(x)=f(x)\cdot x$.

$\displaystyle\Delta(T)$ $\displaystyle\geq
3(y_{uw}+y_{vw}-y_{uvw})y_{uv}+f(x_{vw})(y_{uw}+y_{uv}-y_{uw}y_{uv})(1-y_{vw})$
$\displaystyle\quad+f(x_{uw})(y_{vw}+y_{uv}-y_{vw}y_{uv})(1-y_{uw})$
$\displaystyle=f(x_{vw})y_{uw}+f(x_{uw})y_{vw}+(f(x_{uw})+f(x_{a,c}))y_{uv}+(3-f(x_{uw})-f(x_{vw}))(y_{uw}+y_{vw})y_{uv}$
$\displaystyle\quad-(f(x_{uw})+f(x_{vw}))y_{uw}y_{vw}(1-y_{uv})-3y_{uvw}y_{uv}.$
$\displaystyle\mathrm{cost}(T)$
$\displaystyle=y_{uvw}+y_{uw}+y_{uv}-2y_{uw}y_{uv}+y_{vw}+y_{uv}-2y_{vw}y_{uv}=y_{uvw}+y_{uw}+y_{vw}+2y_{uv}-2(y_{uw}+y_{vw})y_{uv}.$

The difference between the cost and the budget is at least,

$\displaystyle\Delta(T)-\mathrm{cost}(T)\geq(f(x_{vw})-1)y_{uw}+(f(x_{uw})-1)y_{vw}+(f(x_{uw})+f(x_{a,c})-2)y_{uv}$
$\displaystyle+(5-f(x_{uw})-f(x_{vw}))(y_{uw}+y_{vw})y_{uv}-(f(x_{uw})+f(x_{vw}))y_{uw}y_{vw}(1-y_{uv})-3y_{uvw}y_{uv}-y_{uvw}.$
(24)

We can decrease $y_{uv}$ until $y_{uv}=y_{uvw}$.

######  Claim 31.

(24) is increasing with $y_{uv}$.

###### Proof..

We will show that the derivative of (24) w.r.t. $y_{uv}$ is non-negative. The
derivative of (24) w.r.t. $y_{uv}$ is equal to

$\displaystyle(5-f(x_{uw})-f(x_{vw})))(y_{uw}+y_{vw})+(f(x_{uw})+f(x_{vw})-2)+(f(x_{uw})+f(x_{vw}))(y_{uw}y_{vw})-3y_{uvw}.$
(25)

Observe that $f(x)\leq 3$ and $f(x)\geq 2$ if $x\geq\frac{1}{2}$. Hence, if
$x_{uw},x_{vw}\geq\frac{1}{2}$,

$\displaystyle\eqref{equ:1.5deriv}\geq-(y_{uw}+y_{vw})+2+4(y_{uw}y_{vw})-3y_{uvw}\geq
1+4y^{2}_{uvw}-3y_{uvw}\geq 0.$

Note that $f(x)\leq 2$ if $x\leq\frac{1}{2}$ and $f(x)\geq\frac{3}{2}$ if
$x\geq\frac{1}{3}$. Hence, If $\frac{1}{3}\leq x_{uw}\leq\frac{1}{2}$ and
$x_{vw}\geq\frac{1}{3}$, then,

$\displaystyle\eqref{equ:1.5deriv}\geq 1+3(y_{uw}y_{vw})-3y_{uvw}\geq
1+3y^{2}_{uvw}-3y_{uvw}+1+3y_{uvw}(1-y_{uvw})\geq 0.$

$\Diamond$

Substituting $y_{uvw}=y_{uv}$ into (24) yields,

$\displaystyle(f(x_{vw})-1)y_{uw}+(f(x_{uw})-1)y_{vw}+(5-f(x_{uw})-f(x_{vw}))(y_{uw}+y_{vw})y_{uv}$
$\displaystyle+(f(x_{uw})+f(x_{vw})-3)y_{uv}-(f(x_{uw})+f(x_{vw}))y_{uw}y_{vw}(1-y_{uv})-3y^{2}_{uv}.$
(26)

We have to show that (26) is non-negative. For $y_{uv}$ we have the
constraints $y_{uv}=y_{uvw}\leq\min\\{y_{uw},y_{vw}\\}$ and
$y_{uv}\geq(y_{uw}+y_{vw}-1)_{+}$. (26) is a quadratic in $y_{uv}$ with
leading coefficient $-3$. Hence, (26) is minimized either by
$y_{uv}=(y_{uw}+y_{vw}-1)_{+}$ or by $y_{uv}=\min\\{y_{uw},y_{vw}\\}$.

#### Case 1: $y_{uv}=0$.

In this case,

$\displaystyle\eqref{equ:1.5diff1}=(f(x_{vw})-1)y_{uw}+(f(x_{uw})-1)y_{vw}-(f(x_{uw})+f(x_{vw}))y_{uw}y_{vw}.$
(27)

If $x_{uw},x_{vw}\geq\frac{1}{2}$, then,

$\displaystyle\eqref{equ:1.5diff2}$
$\displaystyle=f(x_{vw})(y_{uw}-y_{uw}y_{vw})+f(x_{uw})(y_{vw}-y_{uw}y_{vw})-(y_{uw}+y_{vw})$
$\displaystyle\geq
2(y_{uw}-y_{uw}y_{vw})+2(y_{vw}-y_{uw}y_{vw})-(y_{uw}+y_{vw})$
$\displaystyle=y_{uw}+y_{vw}-4y_{uw}y_{vw}$ $\displaystyle\geq 0.$

For the last inequality we used that $y_{uw},y_{vw}\leq\frac{1}{2}$ and hence,
$y_{uw}\geq 2y_{uw}y_{vw}$. Otherwise, we can assume w.l.o.g. that $x\coloneqq
x_{vw}\leq\frac{1}{2}\leq 1-x\leq x_{uw}=:y$, since $1\geq
y_{uv}+y_{uw}+y_{vw}-2y_{uvw}=y_{uv}+y_{uw}$.

######  Claim 32.

(27) is increasing with $y=x_{uw}$.

###### Proof..

The derivative of (27) w.r.t. $y$ is

$\displaystyle\frac{(2y+y^{2})(7+x-12x^{2})+6x^{2}-x-1}{(y+1)^{2}(x+1)}\geq
0.$

The inequality holds since for $y\geq\frac{1}{2}$ and $x\leq\frac{1}{2}$, the
numerator is bounded by

$(2y+y^{2})(7+x-12z^{2})+6x^{2}-x-1\geq\frac{31}{4}+\frac{1}{4}x-9x^{2}\geq
0.$

$\Diamond$

Hence, (27) is minimized for $y=(1-x)$,

$\displaystyle\eqref{equ:1.5diff2}\geq(f(1-y)-1)(1-y)+(f(y)-1)y-(f(y)+f(1-y))y(1-y).$
(28)

######  Claim 33.

(28) is decreasing with $y$.

###### Proof..

The derivative of (28) w.r.t $y$ is

$\frac{6(2y-1)(2y^{4}-4y^{3}-6y^{2}+8y+5)}{(y-2)^{2}(y+1)^{2}}\geq 0,$

since $(2y-1)\geq 0$ for $y\geq\frac{1}{2}$ and
$(2y^{4}-4y^{3}-6y^{2}+8y+5)\geq 0$. $\Diamond$

Thus, (28) is minimized for $y=\frac{1}{2}$. We have that
$y=x_{uw},x=x_{vw}=\frac{1}{2}$. As before,

$\eqref{equ:1.5diff3}=\left(f\left(\frac{1}{2}\right)-1\right)\frac{1}{2}+\left(f\left(\frac{1}{2}\right)-1\right)\frac{1}{2}-\left(f\left(\frac{1}{2}\right)+\left(\frac{1}{2}\right)\right)\frac{1}{4}=0.$

#### Case 2: $y_{uw}+y_{vw}\geq 1$ and $y_{uv}=y_{uw}+y_{vw}-1$.

In this case,

$\displaystyle\eqref{equ:1.5diff1}=(f(x_{vw})-1)y_{uw}+(f(x_{uw})-1)y_{vw}+(5-f(x_{uw})-f(x_{vw}))(y_{uw}+y_{vw})(y_{uw}+y_{vw}-1)$
$\displaystyle+(f(x_{uw})+f(x_{vw})-3)(y_{uw}+y_{vw}-1)$
$\displaystyle-(f(x_{uw})+f(x_{vw}))y_{uw}y_{vw}(2-(y_{uw}+y_{vw}))-3(y_{uw}+y_{vw}-1)^{2}.$
(29)

Setting $y\coloneqq x_{uw}$ and $x\coloneqq x_{vw}$, we get

$\displaystyle\eqref{equ:1.5diff7}=\left(\frac{6x}{1+x}-1\right)(1-y)+\left(\frac{6y}{1+y}-1\right)(1-y)+\left(5-\frac{6y}{1+y}-\frac{6x}{1+x}\right)(2-y-x)(1-y-x)$
$\displaystyle+\left(\frac{6y}{1+y}+\frac{6x}{1+x}-3\right)(1-y-x)-\left(\frac{6y}{1+y}+\frac{6x}{1+x}\right)(1-y)(1-x)(y+x)-3(1-y-x)^{2}$
$\displaystyle=\frac{2-3x+3x^{2}+2x^{3}-2y^{3}(-1+2x+6x^{2})+y^{2}(3+7x-8x^{2}-12x^{3})-y(3+4x-7x^{2}+4x^{3})}{(1+y)(1+x)}.$
(30)

Since $x+y\leq 1$, we can assume w.l.o.g. that $y\leq\frac{1}{2}$.

######  Claim 34.

(30) is decreasing with $y$.

###### Proof..

The derivative of (30) w.r.t. $y$ is equal to

$\displaystyle\frac{4y^{3}(-1+2x+6x^{2})+y^{2}(-9+5x+44x^{2}+12x^{3})+2y(-3-7x+8x^{2}+12x^{3})+5+x-4x^{2}+6x^{3}}{-(1+y)^{2}(1+x)}.$
(31)

(31) is less than or equal to $0$ if and only if the numerator is non-
negative. Since $x\geq\frac{1}{3}$,

$\displaystyle(-1+2x+6x^{2})\geq\frac{1}{3},$
$\displaystyle(-9+5x+44x^{2}+12x^{3})\geq-2,$
$\displaystyle(-3-7x+8x^{2}+12x^{3})\geq-4,$
$\displaystyle(5+x-4x^{2}+6x^{3})\geq\frac{46}{9}.$

Thus, the numerator of (31) is lower bounded by

$\frac{4}{3}y^{3}-2y^{2}-8y+\frac{46}{9}\geq 0.$

The inequality holds for $y\leq\frac{1}{2}$. $\Diamond$

(30) is minimized for $y=1-x$. This implies that
$y_{uv}=1-x_{uw}-x_{vw}=1-x-y=0$ as in Case 1.

#### Case 3: $y_{uv}=\min\\{y_{uw},y_{vw}\\}$.

Assume that $y_{uv}=y_{uw}\leq y_{vw}$. We will use the lower bound
$f(x)\geq\frac{3}{2}x$ for $x\geq\frac{1}{3}$,

$\displaystyle\eqref{equ:1.5diff1}\geq\frac{1}{2}y_{uw}+\frac{1}{2}y_{vw}+2(y_{uw}+y_{vw})y_{uw}-3y_{uw}y_{vw}(1-y_{uw})-3y^{2}_{uw}$
(32)

The coefficient of $y_{vw}$ in (32) is $\frac{1}{2}-y_{uw}+3y^{2}_{uw}\geq 0$.
Hence, (32) is minimized for $y_{vw}=y_{uw}$,

$\displaystyle\eqref{equ:1.5diff5}\geq y_{uw}-2y^{2}_{uw}+3y^{3}_{uw}\geq 0,$

for $y_{uw}\geq 0$. ∎

##  6 Triangle Analysis used in 1.49-Approximation: Proof of Lemma 10

In this section we will prove Lemma 10. The only type of triangles for which
the budget functions $b^{+}_{1.5}$ and $b^{-}_{1.5}$ are tight (i.e., for
which $\Delta(T)=\mathrm{cost}(T)$), are $+\\!+\\!-$ triangles with value
$0.5$ for the $+$edges and value $1$ for the $-$edge. If we start to decrease
$\alpha$ to be less than $1.5$, the inequality $\Delta(T)\geq\mathrm{cost}(T)$
for budgets $b^{+}_{\alpha}$ and $b^{-}_{\alpha}$ will be violated on tight
triangles $T$. However, similar to [CLN22], we will charge these bad triangles
(i.e., triangles that are close to the tight case) to other triangles that
have some slack (i.e., triangles for which $\Delta(T)-\mathrm{cost}(T)>0$).
Therefore, using a charging argument, we can decrease the approximation ratio
from $1.5$ to $\alpha=\frac{70}{47}\approx 1.49$. This motivates the following
definitions used in [CLN22].

######  Definition 35 (Bad and chargeable triangles).

Let $\eta=1/12$,

  * •

A $+\\!+\\!-$ triangle $T=(u,v,w)$ is a bad triangle centered at $u$ if
$x_{uv},x_{uw}\in[0.5-\eta,0.5+\eta]$ and $x_{vw}\geq 1-\eta$.

  * •

A triangle $T=(u,v,w)$ is a chargeable triangle centered at $u$ if it has two
$+$edges with value $x_{uv},x_{uw}\in[0.5-\eta,0.5+\eta]$ and a third edge
with value $x_{vw}\leq 1-\eta$. A chargeable triangle is either a $+\\!+\\!-$
triangle or a $+\\!+\\!+$ triangle.

  * •

Note that chargeable $+\\!+\\!-$ triangles and bad triangles are only centered
at one vertex, while a chargeable $+\\!+\\!+$ triangle can be centered at
either one or all three vertices.

  * •

A $+$edge $uv$ is a chargeable degenerate triangle if
$x_{uv}\in[0.5-\eta,0.5+\eta]$. We say that the degenerate triangle $uv$ is
centered at both $u$ and $v$.

The following lemma says that the number of chargeable triangles is close to
the number of bad triangles. This enables us to charge the loss we incur on
bad triangles (i.e., the value $\Delta(T)-\mathrm{cost}(T)<0$) to chargeable
triangles with value $\Delta(T)-\mathrm{cost}(T)>0$.

######  Lemma 36 ([CLN22]).

For any vertex $v$, the number of bad triangles centered at $v$ is at most the
number of chargeable triangles (degenerate and non-degenerate) centered at
$v$.

Starting with triangles that are neither bad nor chargeable, we can show that
for these triangles, $\Delta(T)$ remains larger than or equal to
$\mathrm{cost}(T)$ when lowering $\alpha$.

######  Lemma 37.

Fix budget functions $b^{+}\equiv b^{+}_{\alpha}$ and $b^{-}\equiv
b^{-}_{\alpha}$, where $\alpha=\frac{70}{47}$. For any triangle $T$ that is
neither chargeable nor bad, we have $\mathrm{cost}(T)\geq\Delta(T)$.

For bad triangles this is not the case, however, we can give a lower bound
which is negative.

######  Lemma 38.

Fix budget functions $b^{+}\equiv b^{+}_{\alpha}$ and $b^{-}\equiv
b^{-}_{\alpha}$, where $\alpha=\frac{70}{47}$. For any bad triangle $T$, we
have $\Delta(T)-\mathrm{cost}(T)\geq-\frac{1}{36}$.

Next, we have to deal with chargeable triangles.

######  Lemma 39.

Fix budget functions $b^{+}\equiv b^{+}_{\alpha}$ and $b^{-}\equiv
b^{-}_{\alpha}$, where $\alpha=\frac{70}{47}$.

  * •

For any chargeable $+\\!+\\!+$ triangle $T$, we have
$\Delta(T)-\mathrm{cost}(T)\geq\frac{1}{12}$.

  * •

For any chargeable $+\\!+\\!-$ triangle $T$, we have
$\Delta(T)-\mathrm{cost}(T)\geq\frac{1}{36}$.

  * •

For any chargeable degenerate triangle $T$, we have
$\Delta(T)-\mathrm{cost}(T)\geq\frac{1}{18}$.

Before proving the statements above, we show how to combine them to prove
Lemma 10.

###### Proof of Lemma 10.

We have to show the following inequality.

$\displaystyle\eqref{eq:triangle-
sum}=\sum_{uvw\in\binom{V^{\prime}}{3}}\mathrm{cost}(u,v,w)+\sum_{uv\in\binom{V^{\prime}}{2}}\mathrm{cost}(u,v)\leq\sum_{uvw\in\binom{V^{\prime}}{3}}\Delta(u,v,w)+\sum_{uv\in\binom{V^{\prime}}{2}}\Delta(u,v).$

Let $C^{+++}\subseteq\binom{V^{\prime}}{3}$,
$C^{++-}\subseteq\binom{V^{\prime}}{3}$ and
$C^{+}\subseteq\binom{V^{\prime}}{2}$ be the set of chargeable $+\\!+\\!+$,
chargeable $+\\!+\\!-$ and chargeable degenerate triangles, respectively.
Define $C\coloneqq C^{+++}\cup C^{++-}\cup C^{+}$ to be the set of chargeable
triangles and define $B\subseteq\binom{V^{\prime}}{3}$ to be the set of bad
triangles. For all triangles $T$ that are neither bad nor chargeable, we have
by Lemma 37 that $\Delta(T)\geq\mathrm{cost}(T)$. Thus,

$\displaystyle\sum_{T\in\binom{V^{\prime}}{3}}\big{(}\Delta(T)-\mathrm{cost}(T)\big{)}+\sum_{uv\in\binom{V^{\prime}}{2}}\big{(}\Delta(u,v)-\mathrm{cost}(u,v)\big{)}\geq\sum_{T\in
B}\big{(}\Delta(T)-\mathrm{cost}(T)\big{)}+\sum_{T\in
C}\big{(}\Delta(T)-\mathrm{cost}(T)\big{)}.$

By Lemma 38 and Lemma 39,

$\displaystyle\sum_{T\in B}\big{(}\Delta(T)-\mathrm{cost}(T)\big{)}+\sum_{T\in
C}\big{(}\Delta(T)-\mathrm{cost}(T)\big{)}$ $\displaystyle\geq$
$\displaystyle\sum_{T\in B}-\frac{1}{36}+\sum_{T\in
C^{+++}}\frac{1}{12}+\sum_{T\in C^{++-}}\frac{1}{36}+\sum_{T\in
C^{+}}\frac{1}{18}.$

For a fixed vertex $v$, let $B_{v}$, $C^{+++}_{v}$, $C^{++-}_{v}$, $C^{+}_{v}$
be the bad triangles, chargeable $+\\!+\\!+$ triangles, chargeable $+\\!+\\!-$
triangles and chargeable degenerate triangles centered at $v$, respectively.
Remember that bad triangles and chargeable $+\\!+\\!-$ triangles are centered
at one vertex. Moreover, degenerate triangles are centered at their endpoints
and $+\\!+\\!+$ triangles can be centered at each of their three vertices.

$\displaystyle\sum_{T\in B}-\frac{1}{36}+\sum_{T\in
C^{+++}}\frac{1}{12}+\sum_{T\in C^{++-}}\frac{1}{36}+\sum_{T\in
C^{+}}\frac{1}{18}.$ $\displaystyle\geq$ $\displaystyle\sum_{v\in
V^{\prime}}\sum_{T\in B(v)}-\frac{1}{36}+\frac{1}{3}\sum_{T\in
C^{+++}_{v}}\frac{1}{12}+\sum_{T\in
C^{++-}_{v}}\frac{1}{36}+\frac{1}{2}\sum_{T\in C^{+}_{v}}\frac{1}{18}\geq 0.$

The last inequality holds by Lemma 36. ∎

In order to prove Lemmas 37, 38 and 39 we will again consider each type of
triangle individually. The case of $-\\!-\\!-$ triangles, $+\\!-\\!-$
triangles and (non-chargeable) degenerate triangles are already handled in
Section 5. In particular, Lemma 27, Lemma 28 and Lemma 25 show that in these
cases $\Delta(T)\geq\mathrm{cost}(T)$ as long as $\alpha\geq\frac{4}{3}$.
Hence, we only need to improve the analysis for $+\\!+\\!+$, $+\\!+\\!-$
triangles and chargeable degenerate triangles. For $\alpha=\frac{70}{47}$, the
budget functions are equal to,

$\displaystyle b^{+}(x):=\frac{70}{12}\frac{x^{2}}{1+x},\qquad\text{and}\qquad
b^{-}(x):=\frac{35}{12}\frac{(1+2x)(1-x)}{(1+x)},\qquad\forall x\in[0,1].$

#### Degenerate triangles

######  Lemma 40.

Fix the budget function $b^{+}\equiv b^{+}_{\alpha}$, where
$\alpha=\frac{70}{47}$. For any chargeable degenerate triangle $T$, we have
that $\Delta(T)-\mathrm{cost}(T)\geq\frac{1}{18}$.

###### Proof.

Let $T=(u,v)$ be a chargeable degenerate triangle. By definition, $uv$ is a
$+$edge and we have that $x_{uv}\geq 0.5-\eta$. Thus,

$\displaystyle\Delta(T)-\mathrm{cost}(T)\geq\frac{175}{102}x-x\geq\frac{365}{1224}\geq\frac{1}{18}.$

∎

###  6.1 $+\\!+\\!+$ triangles

#### (s,s,s)

$\mathrm{cost}(T)=0$ and $\Delta(T)\geq 0$.

#### (s,s,l)

######  Lemma 41.

Fix the budget function $b^{+}\equiv b^{+}_{\alpha}$, where
$\alpha=\frac{70}{47}$. For any $+\\!+\\!+$ triangle $T$ with one long
$+$edge, we have $\mathrm{cost}(T)\leq\Delta(T)$.

###### Proof.

For a $+\\!+\\!+$ triangle $T=(u,v,w)$, assume that $uv$ is long and $uw$,
$vw$ are short:

$\displaystyle\mathrm{cost}(T)$ $\displaystyle=2\cdot x_{uv},$
$\displaystyle\Delta(T)$
$\displaystyle=b^{+}(x_{uv})+b^{+}(x_{uw})+b^{+}(x_{vw})\geq
b^{+}(x_{uv})+2\cdot b^{+}\left(\frac{x_{uw}+x_{vw}}{2}\right)\geq
b^{+}(x_{uv})+2\cdot b^{+}\left({\frac{x_{uv}}{2}}\right).$

Here, we used Lemma 24 together with the triangle inequality, $x_{uv}\leq
x_{uw}+x_{vw}$. For $x_{uv}\geq 1/3$, we have that,

$\displaystyle b^{+}(x_{uv})+2\cdot
b^{+}\left({\frac{x_{uv}}{2}}\right)\geq\left(\frac{70}{12}\cdot\frac{x_{uv}}{1+x_{uv}}+\frac{70}{12}\cdot\frac{\frac{x_{uv}}{2}}{1+\frac{x_{uv}}{2}}\right)x_{uv}\geq\frac{55}{24}x_{uv}\geq
2x_{uv}.$

∎

#### (s,l,l)

######  Lemma 42.

Fix the budget function $b^{+}\equiv b^{+}_{\alpha}$, where
$\alpha=\frac{70}{47}$. For any $+\\!+\\!+$ triangle $T$ with two long
$+$edges, we have $\Delta(T)-\mathrm{cost}(T)\geq\frac{1}{12}$.

###### Proof.

For a $+\\!+\\!+$ triangle $T=(u,v,w)$, assume that $uv$ is short and $uw$ and
$vw$ are long:

$\displaystyle\mathrm{cost}(T)$
$\displaystyle=x_{uw}+x_{vw}+y_{vw}+y_{uw}-2\cdot y_{uvw}=2-2\cdot y_{uvw}$
$\displaystyle\Delta(T)$
$\displaystyle=b^{+}(x_{uw})+b^{+}(x_{vw})+b^{+}(x_{uv})\cdot(y_{vw}+y_{uw}-y_{uvw}).$
$\displaystyle\Delta(T)-\mathrm{cost}(T)$
$\displaystyle=b^{+}(x_{uw})+b^{+}(x_{vw})+b^{+}(x_{uv})\cdot(y_{vw}+y_{uw}-y_{uvw})-2+2\cdot
y_{uvw}.$ (33)

The derivative of (33) w.r.t. $y_{uvw}$ is

$\displaystyle 2-b^{+}(x_{uv})\geq 2-\frac{35}{12}\cdot\frac{1}{6}\geq 0.$

For the first inequality we used that $x_{uv}\leq\frac{1}{3}$. Hence, (33) is
increasing with $y_{uvw}$. Since
$y_{uvw}\geq\frac{y_{uv}+y_{uw}+y_{vw}-1}{2}$, (33) is minimized for
$y_{uvw}=\max\\{\frac{y_{uv}+y_{uw}+y_{vw}-1}{2},0\\}$.

#### Case 1: $y_{uv}+y_{uw}+y_{vw}-1\geq 0$ and
$y_{uvw}=\frac{y_{uv}+y_{uw}+y_{vw}-1}{2}$.

$\displaystyle\eqref{equ:1.49diff18}$ $\displaystyle\geq
b^{+}(x_{uw})+b^{+}(x_{vw})+b^{+}(x_{uv})\cdot\left(y_{vw}+y_{uw}-\frac{y_{uv}+y_{uw}+y_{vw}-1}{2}\right)-2+y_{uv}+y_{uw}+y_{vw}-1$
(34) $\displaystyle\geq\frac{35}{24}\cdot x_{uw}+\frac{35}{24}\cdot
x_{vw}+b^{+}(x_{uv})\cdot\left(1-\frac{x_{vw}+x_{uw}-x_{uv}}{2}\right)-(x_{uv}+x_{uw}+x_{vw})$
(35)

For the last inequality we used that for $x\geq 1/3$,

$b^{+}(x)\geq\frac{35}{24}\cdot x_{uw}.$

The derivative of (35) w.r.t. $x_{uw}$ is

$\displaystyle\frac{35}{24}-\frac{1}{2}\cdot
b^{+}(x_{uv})-1\geq\frac{35}{24}-\frac{1}{2}\cdot\frac{35}{72}-1\geq 0.$

For the first inequality we used that $x_{uv}\leq\frac{1}{3}$ and that
$b^{+}(x)$ is increasing with $x$. Thus, (35) is increasing with $x_{uw}$. By
symmetry, the same is true for $x_{vw}$. Therefore, (35) is minimized for
$x_{uw}=x_{vw}=\frac{1}{3}$.

$\displaystyle\eqref{equ:1.49diff19}\geq\frac{35}{36}+b^{+}(x_{uv})\cdot\left(1-\frac{1}{2}+\frac{x_{uv}}{2}\right)-\left(\frac{2}{3}+x_{uv}\right)=\frac{1}{16}(105x_{uv}^{2}-36x_{uv}+11)\geq\frac{277}{560}\geq\frac{1}{12}.$

#### Case 2: $y_{uvw}=0$.

$\displaystyle\eqref{equ:1.49diff18}$
$\displaystyle=b^{+}(x_{uw})+b^{+}(x_{vw})+b^{+}(x_{uv})\cdot(y_{vw}+y_{uw})-2.$
(36)

(36) is increasing with $x_{uv}$. Moreover, $x_{uv}$ is lower bounded by
$2-(x_{uw}+x_{vw})$ since $1\geq
y_{uv}+y_{uw}+y_{vw}-2y_{uvw}=y_{uv}+y_{uw}+y_{vw}$. Hence,

$\displaystyle\eqref{equ:diff9}$ $\displaystyle\geq
b^{+}(x_{uw})+b^{+}(x_{vw})+b^{+}(2-(x_{uw}+x_{vw}))\cdot(y_{vw}+y_{uw})-2$
$\displaystyle\geq
2b^{+}\left(\frac{x_{uw}+x_{vw}}{2}\right)+b^{+}(2-(x_{uw}+x_{vw}))\cdot(2-(x_{vw}+x_{uw}))-2$

For the last inequality we used Lemma 24. Substituting $z=x_{uw}+x_{vw}$,

$\displaystyle\eqref{equ:diff9}$ $\displaystyle\geq
2b^{+}\left(\frac{z}{2}\right)+b^{+}(2-z)\cdot(2-z)-2$
$\displaystyle=\frac{35z^{4}-105z^{3}-117z^{2}+572z-488}{6(z-3)(z+2)}\geq\frac{1}{12}$
(37)

The inequality holds for $2\geq z=x_{uw}+x_{vw}\geq 2-x_{uv}\geq
2-\frac{1}{3}=\frac{5}{3}$. ∎

#### (l,l,l)

######  Lemma 43.

Fix the budget function $b^{+}\equiv b^{+}_{\alpha}$, where
$\alpha\geq\frac{24}{17}\approx 1.41$. For any $+\\!+\\!+$ triangles $T$ with
three long $+$edges, we have $\mathrm{cost}(T)\leq\Delta(T)$.

###### Proof.

For $\alpha=\frac{24}{17}$ the budget function $b^{+}(x)$ is equal to
$4.8\cdot\frac{x^{2}}{1+x}$. Let $x=x_{uv},y=x_{uw}$ and $z=x_{vw}$. We use
the following notation: $a=y_{uv|w},b=y_{uw|v},c=y_{vw|u},p=y_{uvw}$ and
$q=y_{u|v|w}$. Notice that $a+b+c+p+q=1$. We assume that $x\leq y\leq z$. Our
goal is to show that $\mathrm{cost}(T)\leq\Delta(T)$. For a $+\\!+\\!+$
triangle $T=(u,v,w)$, assume that $x=uv$, $y=uw$ and $z=vw$ and $1/3<x\leq
y\leq z$.

$\displaystyle\mathrm{cost}(T)$ $\displaystyle=y_{uv}+y_{uw}-2\cdot
y_{uvw}+y_{uv}+y_{vw}-2\cdot y_{uvw}+y_{uw}+y_{vw}-2\cdot
y_{uvw}=2\cdot(y_{uv}+y_{uw}+y_{vw})-6y_{uvw}$ $\displaystyle\Delta(T)$
$\displaystyle=b^{+}(x_{vw})\cdot(y_{uv}+y_{uw}-y_{uvw})+b^{+}(x_{uw})\cdot(y_{uv}+y_{vw}-y_{uvw})+b^{+}(x_{uv})\cdot(y_{uv}+y_{uw}-y_{uvw})$

Since $1/3<x=1-a-p$, we have the constraint that $a+p<2/3$. Our goal is to
show

$\displaystyle\frac{4.8\cdot\mathrm{cost}(T)}{\Delta(T)}=\frac{2(1-p-q)}{\frac{(1-a-p)^{2}(1-a-q)}{(2-a-p)}+\frac{(1-b-p)^{2}(1-b-q)}{(2-b-p)}+\frac{(1-c-p)^{2}(1-c-q)}{(2-c-p)}}\leq
4.8,$ (38)

We can fix $p+q$, which means that $a+b+c=1-p-q$. We want to argue that the
denominator of the LHS of (38) is minimized when $r:=a=b=c=(1-p-q)/3$.

######  Claim 44.

For fixed $p\geq 0$ and fixed $q$, the function
$f(a):=\frac{(1-a-p)^{2}(1-a-q)}{(2-a-p)}$ is convex when $a+p<2/3$,
$a,p,q\geq 0$ and $a+p+q\leq 1$.

###### Proof..

We want to show that the second derivative is positive on the specified ranges
for $a,p$ and $q$.

$\displaystyle
f^{\prime\prime}(a)=\frac{2(a^{3}+3a^{2}(p-2)+3a(p-2)^{2}+p^{3}-6p^{2}+11p+q-7)}{(a+p-2)^{3}}.$

Since $a+p<2/3$, the denominator is always negative. So we need to show that
the numerator is also negative.

$\displaystyle 2(a^{3}+3a^{2}(p-2)+3a(p-2)^{2}+p^{3}-6p^{2}+11p+q-7)<0$
$\displaystyle~{}\iff a^{3}+3a^{2}(p-2)+3a(p-2)^{2}+p^{3}-6p^{2}+11p+q<7.$

We can replace $q=1-a-p$ since this is the maximum value for $q$, so we have

$\displaystyle a^{3}+3a^{2}(p-2)+3a(p-2)^{2}+p^{3}-6p^{2}+10p-a<6.$ (39)

We want to prove (39) when $a+p<2/3$ and $a,p\geq 0$. Define

$\displaystyle h(a):=a^{3}+3a^{2}(p-2)+3a(p-2)^{2}+p^{3}-6p^{2}+10p-a.$

We have

$\displaystyle h^{\prime}(a)=3a^{2}+6ap+3p^{2}+11-12a-12p.$

We want to show that $h^{\prime}(a)>0$ when $a+p<2/3$ and $a,p\geq 0$. We have

$\displaystyle 3a^{2}+6ap+3p^{2}+11>8>12(a+p),$

so we conclude that $h^{\prime}(a)>0$ on the desired domain. Therefore, we can
maximize the value of $a$ in order to maximize $h(a)$. We set $a=2/3-p$. This
gives

$\displaystyle(2/3-p)^{3}+3(2/3-p)^{2}(p-2)+3(2/3-p)(p-2)^{2}+p^{3}-6p^{2}+10p-(2/3-p)$
$\displaystyle=$
$\displaystyle~{}\frac{29p}{3}+3(2/3-p)^{2}(p-2)+(2-3p)(p-2)^{2}-4p^{2}-\frac{10}{27}$
$\displaystyle=$ $\displaystyle~{}\frac{134}{27}-p<6,$

as desired. We conclude that the function $f$ is convex on the relevant range
of $a$ and $p$. $\Diamond$

By Claim 44, we know that $f(a)+f(b)+f(c)\geq 3\cdot f(\frac{a+b+c}{3})$, so
the denominator of the LHS of (38) is minimized when $a=b=c$, so set
$r=a=b=c$. Then we have

$\displaystyle\frac{\mathrm{cost}(T)}{\Delta(T)}=\frac{2(1-p-q)}{f(a)+f(b)+f(c)}\leq\frac{2(1-p-q)}{3\cdot
f(\frac{a+b+c}{3})}\leq\frac{2(1-p-q)}{3\frac{(1-r-p)^{2}(1-r-q)}{(2-r-p)}}.$

Setting $r:=(1-p-q)/3$, we obtain

$\displaystyle\frac{\mathrm{cost}(T)}{\Delta(T)}\leq\frac{6(1-p-q)(5-2p+q)}{(2-2p+q)^{2}(2-2q+p)}.$

Notice that $a+p=r+p=(1-p-q)/3+p<2/3$ implies $q<1$, since $p\geq 0$.

######  Claim 45.

For fixed $0\leq p<2/3$ and for $0\leq q<1-p$, the function
$\ell(q):=\frac{6(1-p-q)(5-2p+q)}{(2-2p+q)^{2}(2-2q+p)}$ is maximized when
$q=0$.

###### Proof..

We show that the derivative of $\ell$ is negative for the appropriate range of
$q$.

$\displaystyle\ell^{\prime}(q)=-\frac{6(14p^{3}-3p^{2}(5q+16)+18p(2q+1)+2(q-1)^{2}(q+8))}{(p-2q+2)^{2}(-2p+q+2)^{3}}.$

Notice that the denominator is always positive for the appropriate range of
$p$ and $q$. So we need to show the following holds for $0\leq p\leq 2/3$ and
$0\leq q<1$.

$\displaystyle\ell_{2}(q):=14p^{3}-3p^{2}(5q+16)+18p(2q+1)+2(q-1)^{2}(q+8)>0.$
(40)

If the following inequality holds, then we can conclude that $\ell_{2}$ is
minimized when $q$ is minimized. Taking the derivative with respect to $q$, we
want to show

$\displaystyle\ell_{2}^{\prime}(q)=-15p^{2}+36p+6(q^{2}+4q-5)<0.$ (41)

Since $\ell_{2}^{\prime\prime}(q)=12q+24>0$, we can replace $q$ with its
maximum value $1-p$. Then we have

$\displaystyle\ell_{2}^{\prime}(q)\leq$
$\displaystyle-15p^{2}+36p+6((1-p)^{2}+4(1-p)-5)=-9p^{2}\leq 0.$

So when $q<1$, Inequality (41) holds. Thus, we have that $\ell_{2}$ is
minimizes when $q$ is minimizes, which is when $q=0$. So we have

$\displaystyle\ell_{2}(q)\geq\ell_{2}(0)=14p^{3}-48p^{2}+18p+16.$

Taking the first and second derivatives of this function with respect to $p$,
we have $42p^{2}-96p+18$ and $84p-96<0$ for $p\in[0,1]$, so we conclude that
the function is concave on this domain. Thus, the minimum values occur at the
extreme values, which are $p=0$ and $p=2/3$. So we have
$\ell_{2}(q)>\min\\{16,10.8\\}$. Thus, we conclude that the Inequality (40)
holds. $\Diamond$

Now we can set $q=0$ and define

$\displaystyle h(p):=$
$\displaystyle\frac{6(1-p)(5-2p)}{(2-2p)^{2}(2+p)}=\frac{3(5-2p)}{(2-2p)(2+p)}.$

We are looking for the maximum value of $h(p)$ for $0\leq p<2/3$. We have

$\displaystyle h^{\prime}(p)=$
$\displaystyle\frac{-6p^{2}+30p+3}{2(p^{2}+p-2)^{2}}\text{ and
}h^{\prime\prime}(p)=\frac{6p^{3}-45p^{2}-9p-33}{(p^{2}+p-2)^{3}}.$

and $h^{\prime}(p)>0$, when $p\in[0,1]$. Thus, $h$ is an increasing function
of $p$. Notice that if $q=0$, then $p<1/2$ (and $r=1/6$), because we have
$p+r=p+(1-p)/3<2/3$. Thus, we can conclude that the maximum value $h$ have and
not violate any of the constraints is $h(1/2)=4.8$. This concludes the proof
of Lemma 43. ∎

######  Lemma 46.

Given budget functions $b^{+}\equiv b^{+}_{\alpha}$ where
$\alpha=\frac{70}{47}$. For a $+\\!+\\!+$ triangles $T$ with three long
$+$edges where furthermore, two of the $+$edges have distance
$x\in[0.5-\eta,0.5+\eta]$, we have
$\Delta(T)-\mathrm{cost}(T)\geq\frac{1}{12}$.

###### Proof.

By Lemma 43, we know that $\mathrm{cost}(T)\leq
4.8\cdot\frac{12}{70}\cdot\Delta(T)$. Here, we use that Lemma 43 only requires
a coefficient of $4.8$ but we have a coefficient of $\frac{70}{12}$ since the
lemma provides a strictly bigger $\alpha=\frac{70}{47}>\frac{24}{17}$. Thus,

$\displaystyle\Delta(T)-\mathrm{cost}(T)\geq\left(1-4.8\cdot\frac{12}{70}\right)\Delta(T)=\frac{31}{175}\Delta(T).$

We will conclude the prove by lower bounding $\Delta(T)$. For $T=(u,v,w)$, let
$x_{uv},x_{uw}\in[0.5-\eta,0.5+\eta].$

$\displaystyle\Delta(T)$ $\displaystyle\geq
b^{+}(x_{uv})\cdot(y_{uv}+y_{vw}-y_{uvw})+b^{+}(x_{uw})\cdot(y_{uw}+y_{vw}-y_{uvw})$
$\displaystyle\geq
b^{+}(x_{uv})\cdot(y_{uw}+y_{vw}-y_{uvw})+b^{+}(x_{uw})\cdot(y_{uv}+y_{vw}-y_{uvw})$
$\displaystyle\geq b^{+}(x_{uv})\cdot y_{uw}+b^{+}(x_{uw})\cdot y_{uv}$
$\displaystyle\geq 2\cdot b^{+}(0.5-\eta)\cdot(0.5-\eta)=\frac{4375}{7344}$

We have that
$\Delta(T)-\mathrm{cost}(T)\geq\frac{31}{175}\cdot\frac{4375}{7344}=\frac{775}{7344}\geq\frac{1}{12}$.
∎

###  6.2 $+\\!+\\!-$ triangles

Observe that $+\\!+\\!-$ triangles have to contain two long $+$edges to be bad
or chargeable. Hence, for $+\\!+\\!-$ triangles that contain at most one long
$+$edge, it is enough to prove that $\Delta(T)\geq\mathrm{cost}(T)$.

######  Lemma 47.

Fix budget functions $b^{+}\equiv b^{+}_{\alpha}$ and $b^{-}\equiv
b^{-}_{\alpha}$, where $\alpha=\frac{70}{47}$. For any $+\\!+\\!-$ triangles
$T$ with at most one long $+$edge, we have $\mathrm{cost}(T)\leq\Delta(T)$.

###### Proof.

We distinguish two cases, the triangle contains two short $+$edges or one
short $+$edge.

#### (s,s)

For a $+\\!+\\!-$ triangle $T=(u,v,w)$, assume that $uv$ is a $-$edge and
$uw$, $vw$ are short $+$edges:

$\displaystyle\mathrm{cost}(T)$ $\displaystyle=2x_{uv}+1,$ (42)
$\displaystyle\Delta(T)$
$\displaystyle=b^{-}(x_{uv})+b^{+}(x_{uw})+b^{+}(x_{vw})\geq
b^{-}(x_{uv})+2\cdot b^{+}\left(\frac{x_{uw}+x_{vw}}{2}\right)\geq
b^{-}(x_{uv})+2\cdot b^{+}\left({\frac{x_{uv}}{2}}\right).$ (43)

As above, we used that $b^{+}(x)$ is convex and increasing together with the
triangle inequality, $x_{uv}\leq x_{uw}+x_{vw}$. The derivative of (43) w.r.t.
$x_{uv}$ is less than $0$ for $x_{uv}\geq 0$,

$\frac{70}{12}\cdot\frac{x_{uv}(4+3x_{uv})}{(1+x_{uv})^{2}(2+x_{uv})^{2}}\leq
0.$

Hence, (43) is decreasing with $x_{uv}$. Observe that $x_{uv}\leq
x_{uw}+x_{vw}\leq\frac{2}{3}$. Since the cost is increasing with $x_{uv}$ we
only need to check the case $x_{uv}=\frac{2}{3}$.

$\displaystyle\Delta(T)-\mathrm{cost}(T)\geq
b^{-}\left(\frac{2}{3}\right)+2\cdot
b^{+}\left({\frac{1}{3}}\right)-\frac{7}{3}=0.$

#### (s,l)

For a $+\\!+\\!-$ triangle $T=(u,v,w)$, assume that $uv$ is a $-$edge and $uw$
is a short $+$edge and $vw$ is a long $+$edge:

$\displaystyle\mathrm{cost}(T)$
$\displaystyle=x_{uv}+y_{vw}+y_{vw}+y_{uv}-2y_{vw}y_{uv}=1+2y_{wv}(1-y_{uv})=1+2(1-x_{wv})x_{uv}$
$\displaystyle\Delta(T)$
$\displaystyle=b^{+}(x_{vw})+b^{-}(x_{uv})+b^{+}(x_{uw})(y_{vw}+y_{uv}-y_{vw}y_{uv})$
$\displaystyle=b^{+}(x_{vw})+b^{-}(x_{uv})+b^{+}(x_{uw})(2-x_{vw}-x_{uv}-(1-x_{vw})(1-x_{uv}))$

#### Case 1

$x_{vw}\geq x_{uv}$.

$\displaystyle\Delta(T)$ $\displaystyle\geq
b^{+}(x_{uv})+b^{-}(x_{uv})=\frac{35}{12},$ $\displaystyle\mathrm{cost}(T)$
$\displaystyle=1+2(1-x_{vw})x_{uv}\leq
1+\frac{4}{3}=\frac{7}{3}\leq\frac{35}{12}.$

For the second inequality, we used that $x_{vw}\geq\frac{1}{3}$.

#### Case 2

$x_{vw}\leq x_{uv}$. By triangle inequality we have $x_{uw}\geq
x_{uv}-x_{vw}$. Remember that by Lemma 24 $b^{+}(x)$ is increasing with $x$,

$\Delta(T)\geq
b^{+}(x_{vw})+b^{-}(x_{uv})+b^{+}(x_{uv}-x_{vw})(2-x_{vw}-x_{uv}-(1-x_{vw})(1-x_{uv}))$

For a fixed $z\coloneqq x_{uv}$, define $x\coloneqq x_{vw}\geq\frac{1}{3}$. We
need to argue that the difference

$\displaystyle\Delta(T)-\mathrm{cost}(T)$
$\displaystyle=b^{+}(x)+b^{-}(z)+b^{+}(z-x)(2-x-z-(1-x)(1-z))-1-2(1-x)z$ (44)
$\displaystyle-1-2(1-x)z$ (45)

is non-negative. To this end, we want to prove that (45) is increasing with
$x$. The derivative of (45) w.r.t. $x$ is

$\displaystyle\frac{70x^{5}z-x^{4}z(175z-47)+2x^{3}z(70z^{2}-117z-70)-x^{2}z(35z^{3}-257z^{2}-81z+129)}{6(x+1)^{2}(x-z-1)^{2}}$
$\displaystyle+\frac{-2x(35z^{4}-47z^{3}-82z^{2}-35z-70)-z(35z^{3}+23z^{2}+11z+58)}{6(x+1)^{2}(x-z-1)^{2}}$
(46)

We will show that the numerator of (46) is non-negative,

$\displaystyle
70x^{5}z-x^{4}z(175z-47)+2x^{3}z(70z^{2}-117z-70)-x^{2}z(35z^{3}-257z^{2}-81z+129)$
$\displaystyle-2x(35z^{4}-47z^{3}-82z^{2}-35z-70)-z(35z^{3}+23z^{2}+11z+58)\geq
0.$ (47)

(47) is concave in $x$. Indeed, consider the second derivative,

$\displaystyle
2z(-129+700x^{3}+81z+257z^{2}-35z^{3}-6x^{2}(-47+175z)+6x(-70-117z+70z^{2}))$
(48)

(48) is convex in $x$. The second derivative of (48) is equal to

$\displaystyle 24z(47+350x-175z).$ (49)

(49) is positive since either $x\geq 2/3$ or $z\leq x+\frac{1}{3}$. Hence, to
show that (48) is non-positive we need to check $x=z$, $x=\frac{1}{3}$ and
$x=z-\frac{1}{3}$.

$\displaystyle x=z,\quad\eqref{equ:1.49deriv7}$
$\displaystyle=2z(-129-339z-163z^{2}+35z^{3})\leq 0,$ $\displaystyle
x=\frac{1}{3},\quad\eqref{equ:1.49deriv7}$
$\displaystyle=-\frac{2}{27}z(5717+7281z-10719z^{2}+945z^{3})\leq 0,$
$\displaystyle x=z-\frac{1}{3},\quad\eqref{equ:1.49deriv7}$
$\displaystyle=\frac{2}{27}z(443-4761z-8181z^{2}+945z^{3})\leq 0.$

For all cases we assumed that $\frac{1}{3}\leq z\leq 1$. Since we now know
that (47) is concave in $x$, we only need to check $x=z$, $x=\frac{1}{3}$ and
$x=z-\frac{1}{3}$.

$\displaystyle x=z,\quad\eqref{equ:1.49deriv6}$
$\displaystyle=z(82+59z+12z^{2})\geq 0,$ $\displaystyle
x=\frac{1}{3},\quad\eqref{equ:1.49deriv6}$
$\displaystyle=\frac{1}{243}(11340-12956z+10167z^{2}+10224z^{3}-15120z^{4})\geq
0,$ $\displaystyle x=z-\frac{1}{3},\quad\eqref{equ:1.49deriv6}$
$\displaystyle=\frac{1}{243}(-11340+12104z+13737z^{2}+10539z^{3}+6615z^{4})\geq
0.$

For the first two cases, we assumed $0\leq z\leq 1$. For the third case
$2/3\leq z\leq 1$. We can conclude that (45) is increasing with $x$. Hence, we
can assume that either $x=\frac{1}{3}$ or $x=z-\frac{1}{3}$.

#### Case 2.1 $x=\frac{1}{3}.$

$\displaystyle\eqref{equ:1.49diff22}=\frac{35}{72}+b^{-}(z)+b^{+}\left(z-\frac{1}{3}\right)\left(1-\frac{5}{3}z\right)-1-\frac{4}{3}z$
$\displaystyle=\frac{1458-221z-443z^{2}-1284z^{3}-1260z^{4}}{216(1+z)(2+3z)}\geq
0.$

The inequality is true since the numerator is non-negative for $z\leq
x+\frac{1}{3}=\frac{2}{3}$.

#### Case 2.2 $x=z-1/3.$

$\displaystyle\eqref{equ:1.49diff22}$
$\displaystyle=b^{+}\left(z-\frac{1}{3}\right)+b^{-}(z)+\frac{35}{72}\left(\frac{7}{3}-2z-\left(\frac{4}{3}-z\right)(1-z)\right)-1-2\left(\frac{4}{3}-z\right)z$
$\displaystyle=\frac{1458-587z-1754z^{2}+12z^{3}+981z^{4}}{216(1+z)(2+3z)}\geq
0.$

The inequality holds true since the numerator is non-negative for $0\leq z\leq
1$. ∎

#### (l,l)

The only case that is left are $+\\!+\\!-$ triangles with two long $+$edges.
This case includes the bad triangles as well as chargeable triangles. For a
$+\\!+\\!-$ triangle $T=(a,b,c)$, assume that $bc$ is a $-$edge and $ab$, $ac$
are long $+$edges. Before we start to distinguish between bad triangles,
chargeable triangles and triangles that are neither, we will prove three
claims that will be used in each of the three cases. For $-$edges we use a
coefficient of $\frac{35}{12}$, $b^{-}(x)\coloneqq\frac{35}{12}(1-x)\leq
b^{-}_{\alpha}(x)$. For $+$edges define the coefficient
$f(x)\coloneqq\frac{70}{12}\cdot\frac{x}{1+x}$, $b^{+}(x)=f(x)\cdot x$.

######  Claim 48.

For a $+\\!+\\!-$ triangle $T=(a,b,c)$, $\Delta(T)-\mathrm{cost}(T)$ is
minimized for $y_{bc}=y_{abc}$.

###### Proof..

$\displaystyle\Delta(T)$
$\displaystyle=\frac{35}{12}(y_{ab}+y_{ac}-y_{abc})y_{bc}+f(x_{ac})(y_{ab}+y_{bc}-y_{ab}y_{bc})(1-y_{ac})+f(x_{ab})(y_{ac}+y_{bc}-y_{ac}y_{bc})(1-y_{ab})$
$\displaystyle=f(x_{ac})y_{ab}+f(x_{ab})y_{ac}+(f(x_{ab})+f(x_{a,c}))y_{bc}+(\frac{35}{12}-f(x_{ab})-f(x_{ac}))(y_{ab}+y_{ac})y_{bc}$
$\displaystyle-\left(f(x_{ab})+f(x_{ac}))y_{ab}y_{ac}(1-y_{bc}\right)-\frac{35}{12}y_{abc}y_{bc}.$
$\displaystyle\mathrm{cost}(T)$
$\displaystyle=y_{abc}+y_{ab}+y_{bc}-2y_{ab}y_{bc}+y_{ac}+y_{bc}-2y_{ac}y_{bc}=y_{abc}+y_{ab}+y_{ac}+2y_{bc}-2(y_{ab}+y_{ac})y_{bc}.$

The difference between the cost and the budget is at least,

$\displaystyle\Delta(T)-\mathrm{cost}(T)\geq(f(x_{ac})-1)y_{ab}+(f(x_{ab})-1)y_{ac}+(f(x_{ab})+f(x_{a,c})-2)y_{bc}-\frac{35}{12}y_{abc}y_{bc}-y_{abc}$
$\displaystyle+\left(\frac{35}{12}+2-f(x_{ab})-f(x_{ac})\right)(y_{ab}+y_{ac})y_{bc}-(f(x_{ab})+f(x_{ac}))y_{ab}y_{ac}(1-y_{bc}).$
(50)

We can decrease $y_{bc}$ until $y_{bc}=y_{abc}$. (50) is increasing with
$y_{bc}$. Indeed, we will show that the derivative of (50) w.r.t. $y_{bc}$ is
non-negative. The derivative of (50) w.r.t. $y_{bc}$ is equal to

$\displaystyle\left(\frac{35}{12}+2-f(x_{ab})-f(x_{ac})\right)(y_{ab}+y_{ac})+(f(x_{ab})+f(x_{ac})-2)+(f(x_{ab})+f(x_{ac}))(y_{ab}y_{ac})-\frac{35}{12}y_{abc}$
(51)

Observe that $f(x)\leq\frac{35}{12}$ and $f(x)\geq\frac{35}{18}$ if $x\geq
1/2$. Hence, if $x_{ab},x_{ac}\geq\frac{1}{2}$,

$\displaystyle\eqref{equ:deriv}$
$\displaystyle\geq\left(2-\frac{35}{12}\right)(y_{ab}+y_{ac})+\left(\frac{35}{9}-2\right)+\left(\frac{35}{9}\right)(y_{ab}y_{ac})-\frac{35}{12}y_{abc}$
$\displaystyle\geq\frac{35}{36}+\left(\frac{35}{9}\right)y^{2}_{abc}-\frac{35}{12}y_{abc}\geq
0$

For the second inequality we used that $y_{ab}+y_{ac}\leq 1$ and $y_{abc}\leq
y_{ab},y{ac}$. Note that $f(x)\leq\frac{35}{18}$ if $x\leq\frac{1}{2}$ and
$f(x)\geq\frac{35}{24}$ if $x\geq\frac{1}{3}$. Hence, If $\frac{1}{3}\leq
x_{ab}\leq\frac{1}{2}$ and $x_{ac}\geq\frac{1}{3}$, then,

$\displaystyle\left(\frac{35}{12}+2-\frac{15}{9}\right)(y_{ab}+y_{ac})+(\frac{35}{12}-2)+(\frac{35}{12})(y_{ab}y_{ac})-\frac{35}{12}y_{abc}$
$\displaystyle=$
$\displaystyle\left(\frac{13}{4}\right)(y_{ab}+y_{ac})+\frac{11}{12}+(\frac{35}{12})(y_{ab}y_{ac})-\frac{35}{12}y_{abc}$
$\displaystyle\geq$
$\displaystyle\quad\frac{11}{12}+\frac{35}{12}y^{2}_{abc}+\frac{43}{12}y_{abc}\geq
0.$

For the second inequality we used that $y_{abc}\leq y_{ab},y_{ac}$. $\Diamond$

Substituting $y_{abc}=y_{bc}$ into (50) yields,

$\displaystyle\Delta(T)-\mathrm{cost}(T)\geq(f(x_{ac})-1)y_{ab}+(f(x_{ab})-1)y_{ac}+(2+\frac{35}{12}-f(x_{ab})-f(x_{ac}))(y_{ab}+y_{ac})y_{bc}$
$\displaystyle+(f(x_{ab})+f(x_{ac})-3)y_{bc}-(f(x_{ab})+f(x_{ac}))y_{ab}y_{ac}(1-y_{bc})-\frac{35}{12}y^{2}_{bc}$
(52)

We want to determine a lower bound for (52). For $y_{bc}$ we have the
constraints $y_{bc}=y_{abc}\leq\min\\{y_{ab},y_{ac}\\}$ and
$y_{bc}\geq(y_{ab}+y_{ac}-1)_{+}$. (52) is a quadratic in $y_{bc}$ with
leading coefficient $-\frac{35}{12}$. Hence, (52) is minimized at the
boundaries.

######  Claim 49.

For a $+\\!+\\!-$ triangle $T=(a,b,c)$ with $y_{bc}=\min\\{y_{ab},y_{ac}\\}$,

$\Delta(T)-\mathrm{cost}(T)\geq\frac{5}{6}y_{bc}-\frac{11}{6}y^{2}_{bc}+\frac{35}{12}y^{3}_{bc}\geq
0$

.

###### Proof..

Assume that $y_{bc}=y_{ab}\leq y_{ac}$. We will use the lower bound
$f(x)\geq\frac{35}{24}$ for $x\geq\frac{1}{3}$,

$\displaystyle\eqref{equ:1.49diff6}\geq(\frac{35}{24}-1)y_{ab}+(\frac{35}{24}-1)y_{ac}+2(y_{ab}+y_{ac})y_{ab}+(\frac{35}{12}-3)y_{ab}-\frac{35}{12}y_{ab}y_{ac}(1-y_{ab})-\frac{35}{12}y^{2}_{ab}$
(53)

The coefficient of $y_{ac}$ in (53) is

$\displaystyle\frac{11}{24}-\frac{11}{12}y_{ab}+\frac{35}{12}y^{2}_{ab}\geq 0$

Hence, (53) is minimized for $y_{ac}=y_{ab}$,

$\displaystyle\eqref{equ:1.49diff7}\geq\frac{5}{6}y_{ab}-\frac{11}{6}y^{2}_{ab}+\frac{35}{12}y^{3}_{ab}\geq
0.$

$\Diamond$

######  Claim 50.

Let $L\in[0,1]$. For a $+\\!+\\!-$ triangle $T=(a,b,c)$ with
$y_{bc}=(y_{ab}+y_{ac}-1)\geq L$, $\Delta(T)-\mathrm{cost}(T)$ is minimized
for $y_{bc}=L$.

###### Proof..

Set $x\coloneqq x_{ab}$ and $z\coloneqq x_{ac}$. In this case,

$\displaystyle\eqref{equ:1.49diff6}=(f(z)-1)(1-x)+(f(x)-1)(1-z)+(2+\frac{35}{12}-f(x)-f(z))(2-x-z)(1-x-z)$
$\displaystyle+(f(x)+f(z)-3)(1-x-z)-(f(x)+f(z))(1-x)(1-z)(x+z)-\frac{35}{12}(1-x-z)^{2}.$

This simplifies to

$\displaystyle\eqref{equ:1.49diff6}=-\frac{-23+36z-35z^{2}-24z^{3}+x(36+47z-83z^{2}+46z^{3})}{(12(1+x)(1+z))}$
$\displaystyle-\frac{x^{2}(-35-83z+92z^{2}+140z^{3})+2x^{3}(-12+23z+70z^{2})}{(12(1+x)(1+z))}$
(54)

Since $x+z\leq 1-L\leq 1$, we can assume that $x\leq\frac{1}{2}$. We will show
that (54) is decreasing with $x$. The derivative of (54) w.r.t. $x$ is equal
to

$\displaystyle-\frac{59+11z-48z^{2}+70z^{3}+4x^{3}(-12+23z+70z^{2})}{12(1+x)^{2}(1+z)}$
$\displaystyle-\frac{2x(-35-83z+92z^{2}+140z^{3})+x^{2}(-107+55z+512z^{2}+140z^{3})}{12(1+x)^{2}(1+z)}$
(55)

We will show that the numerator of (55) is non-negative.

$\displaystyle 59+11z-48z^{2}+70z^{3}\geq\frac{1618}{27},$
$\displaystyle-12+23z+70z^{2}\geq\frac{31}{9},$
$\displaystyle-35-83z+92z^{2}+140z^{3}\geq-\frac{1276}{27},$
$\displaystyle-107+55z+512z^{2}+140z^{3}\geq-\frac{718}{27}.$

For all inequalities we used that $\frac{1}{3}$. The numerator of (55) is
lower bounded by

$\displaystyle\frac{2}{27}(809-1276x-359x^{2}+186x^{3})\geq 0.$

The inequality holds for $0\leq x\leq\frac{1}{2}$. We can conclude that (54)
is decreasing with $x$ and hence, minimized for $x=1-L-z$. This implies that
$y_{bc}=1-x_{ab}-x_{ac}=L$. $\Diamond$

Now, we are ready to prove the lower bounds for bad $+\\!+\\!-$ triangles,
chargeable $+\\!+\\!-$ triangles and $+\\!+\\!-$ triangles that are neither.
We will start with bad $+\\!+\\!-$ triangles and since they are the worst case
we will give a lower bound for all $+\\!+\\!-$ triangles.

######  Lemma 51.

Given budget functions $b^{+}\equiv b^{+}_{\alpha}$ and
$b^{-}(x)\equiv\frac{35}{12}(1-x)\leq b_{\alpha}^{-}(x)$, where
$\alpha=\frac{70}{47}$. For any $+\\!+\\!-$ triangles $T$ with two long
$+$edges, we have $\Delta(T)-\mathrm{cost}(T)\geq-\frac{1}{36}$.

###### Proof.

By Claim 48, we know that

$\displaystyle\Delta(T)-\mathrm{cost}(T)\geq(f(x_{ac})-1)y_{ab}+(f(x_{ab})-1)y_{ac}+(2+\frac{35}{12}-f(x_{ab})-f(x_{ac}))(y_{ab}+y_{ac})y_{bc}$
$\displaystyle+(f(x_{ab})+f(x_{ac})-3)y_{bc}-(f(x_{ab})+f(x_{ac}))y_{ab}y_{ac}(1-y_{bc})-\frac{35}{12}y^{2}_{bc}$
(56)

Again, this is a quadratic function with leading coefficient $-\frac{35}{12}$
and thus minimized for either $y_{bc}=y_{abc}=\min\\{y_{ab},y_{ac}\\}$ or
$y_{bc}=(y_{ab}+y_{ac}-1)_{+}$. If $y_{bc}=y_{abc}=\min\\{y_{ab},y_{ac}\\}$,
then by Claim 49, $\Delta(T)-\mathrm{cost}(T)\geq 0$. By Claim 50, we know
that the case $y_{bc}=(y_{ab}+y_{ac}-1)\geq 0$ reduces to the case $y_{bc}=0$,

$\displaystyle\eqref{equ:1.49diff9}\geq(f(x_{ac})-1)y_{ab}+(f(x_{ab})-1)y_{ac}-(f(x_{ab})+f(x_{ac}))y_{ab}y_{ac}.$
(57)

If $x\geq\frac{1}{2}$, then $f(x)\geq\frac{35}{18}$. Thus, for
$x_{ab},x_{ac}\geq\frac{1}{2}$,

$\displaystyle\eqref{equ:1.49diff10}$
$\displaystyle=f(x_{ac})(y_{ab}-y_{ab}y_{ac})+f(x_{ab})(y_{ac}-y_{ab}y_{ac})-(y_{ab}+y_{ac})$
$\displaystyle\geq\frac{35}{18}(y_{ab}-y_{ab}y_{ac})+\frac{35}{18}(y_{ac}-y_{ab}y_{ac})-(y_{ab}+y_{ac})$
$\displaystyle=\frac{17}{18}y_{ab}+\frac{35}{18}y_{ac}-\frac{35}{9}y_{ab}y_{ac}$
$\displaystyle\geq\frac{34}{9}y_{ab}y_{ac}-\frac{35}{9}y_{ab}y_{ac}$
$\displaystyle=-\frac{1}{9}y_{ab}y_{ac}$ $\displaystyle\geq-\frac{1}{36}$

For the second inequality we used that $y_{ab},y_{ac}\leq\frac{1}{2}$ and
hence, $y_{ab}\geq 2y_{ab}y_{ac}$. For the last inequality, we used that
$y_{ab},y_{ac}\leq\frac{1}{2}$. Otherwise, assume w.l.o.g. that $z\coloneqq
x_{ac}\leq\frac{1}{2}\leq 1-z\leq x_{ab}=x$.

######  Claim 52.

(57) is increasing with $x$ if $z\leq\frac{1}{2}+\eta$.

###### Proof..

$\displaystyle\eqref{equ:1.49diff10}=\frac{-12-6z+41z^{2}+x^{2}(41+6z-70z^{2})+6x(-1+z^{2})}{(1+x)(1+z)}.$
(58)

The derivative of (58) w.r.t $x$ is equal to

$\displaystyle\frac{6+6z-35z^{2}+x(82+12z-140z^{2})+x^{2}(41+6z-70z^{2})}{6(1+x)^{2}(1+z)}.$
(59)

We will show that the numerator of (59) is non-negative.

$\displaystyle 6+6z-35z^{2}\geq-\frac{347}{144}$ $\displaystyle
82+12z-140z^{2}\geq\frac{1489}{36}$ $\displaystyle
41+6z-70z^{2}\geq\frac{1}{2}\cdot\frac{1489}{36}$

For all inequalities we used that $\frac{1}{3}\leq z\leq 0.5+\eta$. The
numerator of (59) is lower bounded by

$\displaystyle\frac{-347+5956x+2978x^{2}}{144}\geq 0.$

The inequality holds for $x\geq\frac{1}{3}$. $\Diamond$

Hence, (58) is minimized for $x=(1-z)$,

$\displaystyle\eqref{equ:1.49diff11}\geq(f(1-x)-1)(1-x)+(f(x)-1)x-(f(x)+f(1-x))x(1-x).$
(60)

The derivative of (60) is

$\frac{70}{12}\cdot\frac{(-5+2x+22x^{2}-8x^{3}-10x^{4}+4x^{5})}{(2-z)^{2}(1+x)^{2}}\geq
0,$

The inequality holds since

$-5+2x+22x^{2}-8x^{3}-10x^{4}+4x^{5}\geq 0$

for $x\geq\frac{1}{2}$. Thus, (58) is minimized for $x=\frac{1}{2}$. We have
that $x=x_{ab},z=x_{ac}=\frac{1}{2}$.

$\eqref{equ:1.49diff11}=(f(1/2)-1)\frac{1}{2}+(f(1/2)-1)\frac{1}{2}-(f(1/2)+f(1/2))\frac{1}{4}=-\frac{1}{36}.$

∎

Next, we will deal with $+\\!+\\!-$ triangles that are chargeable. As soon as
the distance of the $-$edge is bounded away from $1$, we can improve the lower
bound.

######  Lemma 53.

Given budget functions $b^{+}\equiv b^{+}_{\alpha}$ and
$b^{-}(x)\equiv\frac{35}{12}(1-x)\leq b_{\alpha}^{-}(x)$, where
$\alpha=\frac{70}{47}$. For a $+\\!+\\!-$ triangles $T$ with two long $+$edges
and distance at most $1-\eta$ for the $-$edge, we have
$\Delta(T)-\mathrm{cost}(T)\geq\frac{1}{36}$.

###### Proof.

By Claim 48, we know that

$\displaystyle\Delta(T)-\mathrm{cost}(T)\geq(f(x_{ac})-1)y_{ab}+(f(x_{ab})-1)y_{ac}+(2+\frac{35}{12}-f(x_{ab})-f(x_{ac}))(y_{ab}+y_{ac})y_{bc}$
$\displaystyle+(f(x_{ab})+f(x_{ac})-3)y_{bc}-(f(x_{ab})+f(x_{ac}))y_{ab}y_{ac}(1-y_{bc})-\frac{35}{12}y^{2}_{bc}$
(61)

As before, (61) is minimized at the boundaries, i.e. for either
$y_{bc}=y_{abc}=\min\\{y_{ab},y_{ac}\\}$ or
$y_{bc}=\max\\{y_{ab}+y_{ac}-1,\eta\\}$. If
$y_{bc}=y_{abc}=\min\\{y_{ab},y_{ac}\\}$, then by Claim 49,

$\displaystyle\Delta(T)-\mathrm{cost}(T)\geq\frac{5}{6}y_{bc}-\frac{11}{6}y^{2}_{bc}+\frac{35}{12}y^{3}_{bc}\geq\frac{1211}{20736}\geq\frac{1}{36}$

The inequality holds since $y_{bc}\geq\eta$. By Claim 50 we know that the case
$y_{bc}=(y_{ab}+y_{ac}-1)\geq\eta$ reduces to the case $y_{bc}=\eta$,

$\displaystyle\eqref{equ:1.49diff13}\geq(f(x_{ac})-1)y_{ab}+(f(x_{ab})-1)y_{ac}+(2+\frac{35}{12}-f(x_{ab})-f(x_{ac}))(y_{ab}+y_{ac})\eta$
$\displaystyle+(f(x_{ab})+f(x_{ac})-3)\eta-(f(x_{ab})+f(x_{ac}))y_{ab}y_{ac}(1-\eta)-\frac{35}{12}\eta^{2}$
$\displaystyle=(f(z)-1)(1-x)+(f(x)-1)(1-z)+(2+\frac{35}{12}-f(x)-f(z))(2-x-z)\eta$
$\displaystyle+(f(x)+f(z)-3)\eta-(f(x)+f(z))(1-x)(1-z)(1-\eta)-\frac{35}{12}\eta^{2}.$
(62)

#### Case 1: $x,z\geq 1/2+\eta$.

We have that $f(x),f(z)\geq 2$,

$\displaystyle\eqref{equ:1.49diff14}\geq(1-x)+(1-z)+(\frac{35}{12}-2)(2-x-z)\eta+\eta-4(1-x)(1-z)(1-\eta)-\frac{35}{12}\eta^{2}$
$\displaystyle\geq\eta-\frac{35}{12}\eta^{2}=\frac{109}{1728}\geq\frac{1}{36}.$

#### Case 2: $z\leq 1/2+\eta$.

######  Claim 54.

(62) is increasing for $x$ if $z\leq 0.5+\eta$.

###### Proof..

$\displaystyle\eqref{equ:1.49diff14}=\frac{-(2507+1487z-11100z^{2}+x(1487+467z-1860z^{2})+60x^{2}(-185-31z+308z^{2}))}{(1728(1+x)(1+z))}.$
(63)

The derivative of (63) w.r.t $x$ is equal to

$\displaystyle
5\frac{17+17z-154z^{2}+x(370+62z-616z^{2})+x^{2}(185+31z-308z^{2})}{144(1+x)^{2}(1+z)}$
(64)

We will lower bound the numerator of (64). Observe that

$\displaystyle 17+17z-154z^{2}\geq-\frac{1835}{72}$ (65) $\displaystyle
370+62z-616z^{2}\geq\frac{1769}{9}$ (66) $\displaystyle
185+31z-308z^{2}\geq\frac{1769}{18}$ (67)

We used that $\frac{1}{3}\leq z\leq 1/2+\eta$ for all of the above
inequalities. Hence, we have that the numerator of (64) is lower bounded by

$\displaystyle 1/72(-1835+14152x+7076x^{2})\geq 0.$

The inequality is true for $x\geq 1/3$. $\Diamond$

Thus, we can assume that $x=1-\eta-z$ since $x+z\geq 1-\eta$.

$\displaystyle\eqref{equ:1.49diff14}$
$\displaystyle\geq(f(1-\eta-z)-1)(\eta+z)+(f(1-\eta-z)-1)(1-z)+(2+\frac{35}{12}-f(1-\eta-z)-f(z))(1+\eta)\eta$
$\displaystyle\quad\quad+(f(1-\eta-z)+f(z)-3)\eta-(f(1-\eta-z)+f(z))(\eta+z)(1-z)(1-\eta)-\frac{35}{12}\eta^{2}$
$\displaystyle=\frac{-32742+115291z-32602z^{2}-203280z^{3}+110880z^{4}}{864(1+z)(-23+12z)}\geq\frac{1343}{20736}\geq\frac{1}{36}.$
(68)

(68) is minimized for $z=0.5-\eta/2$. (68) is convex and first derivative is
$0$ for $z=z=0.5-\eta/2$. Indeed, the derivative of (68) is

$\displaystyle\frac{35(-11+24z)(7823+11132z-9482z^{2}-5808z^{3}+3168z^{4})}{864(1+z)^{2}(-23+12z)^{2}}.$

The second derivative of (68) is equal to

$\displaystyle\frac{385}{18}-\frac{3815}{432(1+z)^{3}}+\frac{15260}{(-23+12z)^{3}}\geq
0.$

The inequality holds for $0\leq z\leq 1$. ∎ If a $+\\!+\\!-$ triangle is
neither chargeable nor bad, it is again enough to show that
$\Delta(T)\geq\mathrm{cost}(T)$. Thus, we complete the previous lemma with the
following.

######  Lemma 55.

Given budget functions $b^{+}\equiv b^{+}_{\alpha}$ and
$b^{-}(x)\equiv\frac{35}{12}(1-x)\leq b_{\alpha}^{-}(x)$, where
$\alpha=\frac{70}{47}$. For a $+\\!+\\!-$ triangles $T$ with two long $+$edges
where one of the $+$edges has distance $x\notin[0.5-\eta,0.5+\eta]$, we have
$\Delta(T)-\mathrm{cost}(T)\geq 0$.

###### Proof.

By Claim 48, we know that

$\displaystyle\Delta(T)-\mathrm{cost}(T)\geq(f(x_{ac})-1)y_{ab}+(f(x_{ab})-1)y_{ac}+\left(2+\frac{35}{12}-f(x_{ab})-f(x_{ac}))(y_{ab}+y_{ac}\right)y_{bc}$
$\displaystyle+(f(x_{ab})+f(x_{ac})-3)y_{bc}-(f(x_{ab})+f(x_{ac}))y_{ab}y_{ac}(1-y_{bc})-\frac{35}{12}y^{2}_{bc}$
(69)

Again, this is a quadratic function with leading coefficient $-\frac{35}{12}$
and thus minimized for either $y_{bc}=y_{abc}=\min\\{y_{ab},y_{ac}\\}$ or
$y_{bc}=(y_{ab}+y_{ac}-1)_{+}$. If $y_{bc}=y_{abc}=\min\\{y_{ab},y_{ac}\\}$,
then by Claim 49, $\Delta(T)-\mathrm{cost}(T)\geq 0$. By Claim 50 we know that
the case $y_{bc}=(y_{ab}+y_{ac}-1)\geq 0$ reduces to the case $y_{bc}=0$. Set
$x=x_{ab}$ and $z=x_{ac}$.

$\displaystyle\eqref{equ:1.49diff16}=(f(z)-1)(1-x)+(f(x)-1)(1-z)-(f(x)+f(z))(1-x)(1-z).$
(70)

Since $x+z\geq 1$ we have either, $x\geq 0.5+\eta$ or $z\geq 0.5+\eta$. Assume
that $x\geq 0.5+\eta$. We distinguish the following two cases.

#### Case 1: $x,z\geq\frac{1}{2}+\eta$.

For $x\geq\frac{1}{2}+\eta$, $f(x)\geq 2$. Thus,

$\displaystyle(f(z)-1)(1-x)+(f(x)-1)(1-z)-(f(x)+f(z))(1-x)(1-z)\geq(1-x)+(1-z)-4(1-x)(1-z)\geq
0.$

For the last inequality we used that $(1-z),(1-x)\leq\frac{1}{2}$.

#### Case 2: $x\geq 0.5+\eta$ and $z\leq 0.5+\eta$.

By Claim 52 we know that (70) is increasing with $x$. Hence, we have either
$x=0.5+\eta$ and $z\geq 0.5-\eta$ or $x=1-z$ and $z\leq 0.5-\eta$. For
$x=1-z$,

$\displaystyle\eqref{equ:1.49diff17}\geq(f(z)-1)z+(f(1-z)-1)(1-z)-(f(1-z)+f(z))z(1-z)$
$\displaystyle=\frac{23-76z+6z^{2}+140z^{3}-70z^{4}}{12+6z-6z^{2}}\geq 0$

The inequality holds since both the numerator and the denominator are non-
negative for $z\leq\frac{1}{2}-\eta$. For $x=0.5+\eta$,

$\displaystyle\eqref{equ:1.49diff17}\geq\frac{-223-570z+2978z^{2}}{1368(1+z)}\geq
0$

The numerator is non-negative for $z\geq\frac{1}{2}-\eta$. ∎

###  6.3 Wrapping up: Deferred proofs of Lemma 37, 38, 39

###### Proof of Lemma 37.

We have to show that $\Delta(T)\geq\mathrm{cost}(T)$ for all triangles $T$
that are neither chargeable nor bad. This is true for $-\\!-\\!-$ triangles,
$+\\!-\\!-$ triangles and degenerate triangles by Lemma 27, Lemma 28 and Lemma
25. Let $T$ be a $+\\!-\\!-$ triangles where $uv$, $uw$ are $+$edges and $vw$
is a $-$edge. If $T$ contains at most one long $+$edge, then the inequality
holds by Lemma 47. Otherwise, assume that both $+$edges are long. $T$ is
neither bad nor chargeable if and only if $x_{vw}\leq 1-\eta$ or at least one
of $x_{uv}$, $x_{uw}$ is not in $[0.5-\eta,0.5+\eta]$. In the first case
$\Delta(T)\geq\mathrm{cost}(T)$ by Lemma 53 and in the second case by Lemma
55. For $+\\!+\\!+$ triangles the statement holds true by Lemma 41 for
triangles with one long $+$edge, by Lemma 42 for triangles with two long
$+$edges and by Lemma 43 for triangles with three long $+$edges. The cost is
$0$ in the case where all $+$edges are short. ∎

###### Proof of Lemma 38.

A bad triangle $T$ is always a $+\\!+\\!-$ triangle with two long $+$edges.
Thus, the bound follows from Lemma 51. ∎

###### Proof of Lemma 39.

Consider a chargeable $+\\!+\\!-$ triangle $T$. Both $+$edges of $T$ are long.
Moreover, the $-$edge has value $x\leq 1-\eta$. Thus,
$\Delta(T)-\mathrm{cost}(T)\geq\frac{1}{36}$ by Lemma 53. A chargeable
$+\\!+\\!+$ triangle $T$ has either two long $+$ edges or three long $+$edges.
In the first case we have $\Delta(T)-\mathrm{cost}(T)\geq\frac{1}{12}$ by
Lemma 42 and in the second case by Lemma 46. For chargeable degenerate
triangles $T$, $\Delta(T)-\mathrm{cost}(T)\geq\frac{1}{18}$ by Lemma 40. ∎

##  7 1.437-Approximation: Computer-assisted proof

In this section, by introducing and solving the factor-revealing SDP, we prove
Lemma 11, which implies that our algorithm archives a $1.437$-approximation.
Let $\mathcal{T}$ be defined as the set of all possible triangles, represented
by tuples of values $(y_{uv},y_{uw},y_{vw},y_{uvw})$ satisfying the condition
$y_{uv}\leq y_{uw}\leq y_{vw}$. We consider positive degenerate triangle $uv$
as a $+\\!+\\!+$ triangle and negative degenerate triangle $uv$ as a
$-\\!-\\!+$ triangle, both having the same $y$ value
$(y_{uv},y_{uv},1,y_{uv})$. This substitution simplifies our computations, and
we will later show that it doesn’t increase the value of
$\Delta(T)-\mathrm{cost}(T)$ for degenerate triangles. Consequently,
$\mathcal{T}$ includes both degenerate and non-degenerate triangles and it can
be used to lower bound $\Delta(T)-\mathrm{cost}(T)$. Given graph $G$ and the
cluster LP solution $z_{S}$, along with their corresponding $y$ values, we
define $\eta_{T}(y)$ for any triangle $T\in\mathcal{T}$ as the number of such
triangles present in graph $G$.

In section 5, we demonstrate that, for any triangle $T\in\mathcal{T}$, the
inequality $\Delta(T)-\mathrm{cost}(T)\geq 0$ holds. In section 6, we
establish that, for any solution $y$, it is possible to determine a reduced
budget such that the summation
$\sum_{T}\eta_{T}(y)\cdot(\Delta(T)-\mathrm{cost}(T))\geq 0$. The key insight
is that $\eta_{T}(y)$ for a given solution $y$ cannot take arbitrary values.
In this section, we elucidate how stronger constraints can be imposed on
$\eta_{T}(y)$, enabling the use of a smaller budget for
$\sum_{T}\eta_{T}(y)\cdot(\Delta(T)-\mathrm{cost}(T))$.

In this section, we will first outline the constraint we intend to impose on
$\eta_{T}$. Subsequently, we will employ discretization techniques to
encompass all possible triangles $T$. We will then formulate a semi-definite
program to demonstrate that it is possible to achieve
$\sum_{T}\eta_{T}(y)\cdot(\Delta(T)-\mathrm{cost}(T))\geq 0$ within a reduced
budget.

#### Covariance Constraint.

Given cluster LP solution $z_{S}$ and $y$, for each node $u$, the covariance
matrix $COV_{u}\in\mathbb{R}^{V\times V}$ where

$\displaystyle COV_{u}(v,w)=y_{uvw}-y_{uv}y_{uw}$

is positive semi-definite(PSD). Actually, we can even show a stronger version
of the covariance constraint.

######  Lemma 56.

We define $y_{S}=\sum_{S^{\prime}\supseteq S}z_{S^{\prime}}$ for every
$S\subseteq V$. For any $T\subseteq V,T\neq\emptyset$, the matrix
$M\in\mathbb{R}^{V\times V}$ where
$M_{uv}=y_{T\cup\\{u,v\\}}-y_{T\cup\\{u\\}}y_{T\cup\\{v\\}}$ is PSD.

###### Proof.

Fix any vector $a\in\mathbb{R}^{V}$. For every $S\subseteq V$, we define
$a(S):=\sum_{v\in S}a_{v}$. Then

$\displaystyle a^{\intercal}Ma$ $\displaystyle=\sum_{u,v\in
V}(y_{T\cup\\{u,v\\}}-y_{T\cup\\{u\\}}y_{T\cup\\{v\\}})a_{u}a_{v}$
$\displaystyle=\sum_{u,v\in V}a_{u}a_{v}\left(\sum_{S\supseteq
T\cup\\{u,v\\}}z_{S}-\Big{(}\sum_{S\supseteq
T\cup\\{u\\}}z_{S}\Big{)}\Big{(}\sum_{S^{\prime}\supseteq
T\cup\\{v\\}}z_{S^{\prime}}\Big{)}\right)$ $\displaystyle=\sum_{S\supseteq
T}z_{S}\cdot a(S)\cdot a(S)-\sum_{S\supseteq T}\sum_{S^{\prime}\supseteq
T}z_{S}\cdot z_{S^{\prime}}\cdot a(S)\cdot a(S^{\prime})$
$\displaystyle\geq\sum_{S\supseteq T,S^{\prime}\supseteq
T}z_{S}z_{S^{\prime}}a^{2}(S)-\sum_{S\supseteq T}\sum_{S^{\prime}\supseteq