}\lambda_{\min}\big{(}A(\operatorname{Ham}_{=}(a,b))\big{)}=\binom{a}{b}\bigg{(}1-\frac{2b}{a}\bigg{)},$

where $A(G)\in\mathbb{S}^{V}$ denotes the adjacency matrix of a graph
$G=(V,E)$. The interest on the smallest eigenvalue of the adjacency matrix in
both works [1, 38] stems directly from 90: since
$G\coloneqq\operatorname{Ham}_{=}(a,b)$ is $\binom{a}{b}$-regular, it follows
that $\lambda_{\max}(L(G))=\binom{a}{b}-\lambda_{\min}(A(G))$.

######  Proposition 30.

For every real number $\beta>\alpha_{\scriptscriptstyle\mathrm{GW}}$ there
exists a graph $G=(V,E)$, as well as witnesses $(\rho,x)$ and $(\mu,Y)$ of the
membership $(\mathbbm{1},\mathbbm{1})\in\mathrm{H}(G)$, satisfying the
following conditions. One has that $\eta(G)=\operatorname{mc}(G)$ and
$\eta^{\circ}(G)=\operatorname{fcc}(G)$. Furthermore,

(92)
$\mathbb{E}\big{(}|\delta(\operatorname{GW}(Y))|\big{)}<\beta\operatorname{mc}(G)\text{
and }\tfrac{1}{\beta}\operatorname{fcc}(G)<y^{\mathsf{T}}\mathbbm{1},$

where $y\in\mathbb{R}_{+}^{\mathcal{P}(V)}$ is defined as in 84.

###### Proof.

By 6, there exists a rational number $\zeta\in(-1,0)$ such that

(93)
$\alpha_{\scriptscriptstyle\mathrm{GW}}\leq\frac{2}{1-\zeta}\frac{\arccos(\zeta)}{\pi}<\beta.$

Let $a\in\mathbb{N}$ be such that $b\coloneqq(1-\zeta)\frac{a}{2}$ is an even
natural number, so that

$\zeta=1-2b/a.$

We now prove the statement holds for $G\coloneqq\operatorname{Ham}_{=}(a,b)$.

Let $U\in\mathbb{R}^{[a]\times V(G)}$ be defined by $Ue_{s}\coloneqq
2s-\mathbbm{1}\in\mathbb{R}^{[a]}$ for every $s\in V(G)=\\{0,1\\}^{[a]}$. We
claim that

(94)
$(\rho,x)\coloneqq(\tfrac{b}{a}|E|,\tfrac{1}{2}\tbinom{a-1}{b-1}\mathbbm{1})\text{
and }(\mu,Y)\coloneqq(\tfrac{a}{b},\tfrac{1}{b}U^{\mathsf{T}}U)\text{ witness
the membership }(\mathbbm{1},\mathbbm{1})\in\mathrm{H}(G).$

Feasibility of $(\tfrac{a}{b},\tfrac{1}{b}U^{\mathsf{T}}U)$ in 11 with
$z\coloneqq\mathbbm{1}$ follows directly from the definition of $U$ and $G$,
since

(95) $Y_{ij}=\tfrac{a}{b}\zeta\qquad\mathrlap{\text{for every }ij\in E,}$

whereas feasibility of $(\rho,x)$ in 4b with $w\coloneqq\mathbbm{1}$ follows
from 91, since $L(G)=\binom{a}{b}I-A(G)$ as $G$ is $\tbinom{a}{b}$-regular. It
is immediate that $\rho\mu=|E|$. Thus, 94 is proved. We claim that

(96) $(\mathbbm{1},\mathbbm{1})\text{ is an exact pairing}.$

Note that, in particular, 96 ensures that $\eta(G)=\operatorname{mc}(G)$ and
$\eta^{\circ}(G)=\operatorname{fcc}(G)$. For every $i\in[a]$, set
$S_{i}\coloneqq\\{\,{s\in\\{0,1\\}^{a}}\,\colon{s_{i}=1}\\}$. One may easily
check that $|\delta(S_{i})|=\binom{a-1}{b-1}2^{a-1}$ for every $i\in[a]$. By
94 and 5, all such cuts are maximum, since

$\eta(G)=\frac{b}{a}|E|=\frac{b}{a}\binom{a}{b}2^{a-1}=\binom{a-1}{b-1}2^{a-1}=|\delta(S_{i})|\leq\operatorname{mc}(G)\leq\eta(G).$

Now consider the fractional cut cover
$\bar{y}\coloneqq\tfrac{1}{b}\sum_{i\in[a]}e_{S_{i}}$. By definition of
$\operatorname{Ham}_{=}(a,b)$, each edge belongs to $b$ of the cuts in
$\\{\,{\delta(S_{i})}\,\colon{i\in[a]}\\}$, so $\sum_{S\subseteq
V}\bar{y}_{S}\mathbbm{1}_{\delta(S)}=\mathbbm{1}$. Hence 94 and 13 imply that
$\bar{y}$ is an optimal fractional cut cover, as

$\frac{a}{b}=\eta^{\circ}(G)\leq\operatorname{fcc}(G)\leq\mathbbm{1}^{\mathsf{T}}\bar{y}=\frac{a}{b}.$

This concludes the proof of 96. By 15, 95, and linearity of expectation,

$\mathbb{E}\big{(}|\delta(\operatorname{GW}(Y))|\big{)}=\sum_{ij\in
E}\mathbb{P}(ij\in\delta(\operatorname{GW}(Y)))=\frac{\arccos(\zeta)}{\pi}|E|.$

Let $y,\,p\in\mathbb{R}_{+}^{\mathcal{P}(V)}$ and $\bar{\nu}\in\mathbb{R}_{+}$
be defined from $(\mu,Y)$ as in 84. Then for every $ij\in E$,

$e_{ij}^{\mathsf{T}}\bigg{(}\,\sum_{S\subseteq
V}p_{S}\mathbbm{1}_{\delta(S)}\bigg{)}=\mathbb{P}(ij\in\delta(\operatorname{GW}(Y)))=\frac{\arccos(\zeta)}{\pi}$

by 15. Hence $\bar{\nu}=\pi/\arccos(\zeta)$. Since $a/b=2/(1-\zeta)$, we have
that

$\frac{\mathbb{E}\big{(}|\delta(\operatorname{GW}(Y))|\big{)}}{\operatorname{mc}(G)}=\frac{2}{1-\zeta}\frac{\arccos(\zeta)}{\pi}=\frac{\operatorname{fcc}(G)}{\mathbbm{1}^{\mathsf{T}}y}<\beta.$

and this number is $<\beta$ by 93. ∎

[25] [25] studied a family of graphs closely related to the one featured in
the proof of Proposition 30, using it to bound the quality of the
approximation factor obtained by [19] [19]. The specific construction in our
proof is a simplification of this work due to [1] [1]. The relevance of
Proposition 30 to our algorithms inherits several aspects of the relevance of
these examples to the maximum cut setting. Let $\beta$ be a real number such
that $\beta>\alpha_{\scriptscriptstyle\mathrm{GW}}$. Proposition 30 presents
an obstruction for the use of the randomized hyperplane technique to produce
$\beta$-certificates. Let $G=(V,E)$ be a graph whose existence is ensured by
the proposition. Then $G$ defines instances where the SDP relaxations 4a and
11 are tight — i.e., the integrality ratio is one —, but where the rounding
itself can be responsible for the approximation factor
$\alpha_{\scriptscriptstyle\mathrm{GW}}$ of the final algorithm. The first
inequality in 92 states that the expected value of a cut produced by the
random hyperplane technique will be too small for the desired approximation
factor $\beta$. The second inequality in 92 does not directly translate to the
setting of our algorithm, which takes finitely many samples and outputs a
surrogate for the $y\in\mathbb{R}_{+}^{\mathcal{P}(V)}$ defined in 84.
Proposition 30 and 87 do imply that, almost surely, the objective value
$\mu_{t}/t$ obtained from 86 deteriorates above
$\tfrac{1}{\beta}\operatorname{fcc}(G)$ for sufficiently large values of
$t\in\mathbb{N}$. Note, however, that similar to how 92 allows for a finite
number of samples to define a fractional cut cover with objective value better
than $\tfrac{1}{\beta}\operatorname{fcc}(G)$, it also allows for a single cut
to have objective value better than $\beta\operatorname{mc}(G)$.

Let $G=(V,E)$ be a graph and let $w\in\mathbb{R}_{+}^{E}$. Propositions 29 and
30 describe limitations of the approach we chose for producing approximation
algorithms for the maximum cut and fractional cut-covering problems. The
_Unique Games Conjecture_ [27] implies that it is NP-hard to compute, given an
instance $(G,w)$ of the maximum cut problem as input, an upper bound to
$\operatorname{mc}(G,w)$ with a better approximation guarantee than 5. Recall
from Remark 10 that this conjectured optimality extends to the SDP in 11 and
the fractional cut-covering problem: obtaining any better approximation factor
on the objective value for Algorithm 1 would disprove the conjecture.

##  6\. Concluding Remarks

We summarize the main contributions of this paper and discuss future
directions. Key to our contributions is precisely describing the relationship
between the (weighted) maximum cut and the weighted fractional cut-covering
problems through the lens of gauge duality: the functions
$\operatorname{mc}(G,\cdot)$ and $\operatorname{fcc}(G,\cdot)$ form a gauge
dual pair. Crucially, the SDP relaxation for the maximum cut problem, utilized
by [19] [19], and the SDP relaxation we provided for the fractional cut-
covering problem share the same property: $\eta(G,\cdot)$ and
$\eta^{\circ}(G,\cdot)$ form a gauge dual pair (see Proposition 7). This
explicit connection establishes the background and foundation for the
development of our algorithms. Gauge duality promptly yields a bound
conversion procedure, enabling us to extend the
$\alpha_{\scriptscriptstyle\mathrm{GW}}$ approximation ratio between
$\operatorname{mc}(G,\cdot)$ and $\eta(G,\cdot)$ to a
$1/\alpha_{\scriptscriptstyle\mathrm{GW}}$ approximation ratio between
$\operatorname{fcc}(G,\cdot)$ and $\eta^{\circ}(G,\cdot)$ (see Proposition 9).

The understanding of this connection organizes our efforts in algorithmic
design:

  1. (i)

Optimal solutions $Y\in\mathbb{S}_{+}^{V}$ of the SDP relaxation 4a for
maximum cut are employed in [19] to sample (the shore of) a cut by the
randomized hyperplane technique, with $Y$ as the generating parameter. We
extend this technique to the fractional cut-covering problem in two stages:
initially by showing that the marginal probabilities for the shores provide a
fractional cut cover with the same approximation quality, and subsequently by
sparsifying our cover through a polynomial-time randomized procedure (see
Propositions 1, 4, and 6).

  2. (ii)

We address the problem of simultaneously obtaining approximate solutions for
the maximum cut and the weighted fractional cut-covering problems with
certificates of approximate optimality. This inspires our definition of the
set $\mathrm{H}(G)$, which precisely links tightness of
$w^{\mathsf{T}}z\leq\eta(G,w)\eta^{\circ}(G,z)$ in gauge duality with the
optimality of solutions for the SDP relaxations. This directly motivates the
definition of $\beta$-pairings and $\beta$-certificates, which are essential
to our simultaneous certification process (see Proposition 15, and Theorems 18
and 19).

  3. (iii)

Given the strong algorithmic focus of our work, it is crucial to deal with the
fact that exact optimal solutions for SDPs may not be computable in polynomial
time. We combine the strategies from the previous items: in Section 3.4, we
introduce the set $\mathrm{H}_{\varepsilon,\sigma}(G)$, which is a perturbed
version of $\mathrm{H}(G)$, and then develop a randomized approximation
algorithm which requires only nearly optimal solutions for the SDPs.

  4. (iv)

When run on a connected graph with $n$ vertices and $m$ edges, our algorithms
rely on obtaining a nearly optimal solution $Y$ to an instance of the relevant
SDP problems, which can be done in $O(m^{4})$ time, followed by the rounding
procedure on $Y$, which involves a single $n\times n$ Cholesky factorization,
$O(n\ln(n))$ samples from a standard Gaussian distributions, and
$O(n^{2}\ln(n))$ extra work.

  5. (v)

Section 5 addresses many aspects of our approach that are optimal. Many of
them are mirror images under gauge duality of corresponding properties for the
Goemans and Williamson’s algorithm for maximum cut (see Proposition 30).

Throughout our work we have assumed the real-number machine model [7] with two
extra oracles: one sampling from a standard normal distribution, and one
computing Cholesky factorizations. This second assumption is equivalent to
assuming exact computation of square roots of real positive numbers. Despite
these assumptions, our results build towards an implementation in the Turing
machine model. Explicitly, the Slater points for 58 used in Appendix C may
allow one to utilize the work of [10] [10] to conclude that both
$\eta_{\varepsilon}$ and $\eta_{\varepsilon}^{\circ}$ may be computed in
polynomial time on a Turing machine. Proposition 22 identifies the main
computational steps required to round these optimal solutions, and it may be
extended to the probabilistic Turing machine model with an appropriate
analysis of approximate square root computations.

The interplay of duality with probabilistic aspects that permeates this work
suggests interesting avenues for future research. Note that, essential to our
approach, Goemans and Williamson’s randomized hyperplane technique casts an
optimal solution $Y$ for 4a as a _distribution_ of cuts. This enables edges
that do not occur in any heavy cut to be probably covered after appropriate
thickening. The SDP perturbation 58b makes this even more robust, since for
any feasible solution $(\mu,Y)$, sampling from $\operatorname{GW}(Y)$ covers
every edge with probability at least $\sqrt{2\varepsilon}/\pi$ (by 62) and $Y$
has full rank. The analysis in [19] for maximum cut relies on expected values,
whereas for fractional cut covers we rely on concentration inequalities (see
Propositions 4 and 21). In this respect, it would be interesting to find a
gauge dual analogue of the analysis in [19, Sec. 3.1], which improves the
approximation factor $\alpha_{\scriptscriptstyle\mathrm{GW}}$ when the maximum
cut is large. A similar question can be made about a gauge dual analogue of
low-rank SDP solutions with improved approximation factors, as in [4]. One may
also ask whether the techniques from [32] can be applied to derandomize our
algorithms.

Further natural research directions include the use of duality in close
relatives of the maximum cut problem, such as maximum bisection problem (see,
e.g., [37, 3]) and Nesterov’s generalization to quadratic optimization
problems [35]. Beyond the maximum cut and fractional cut-covering problems, it
is natural to search for and study other pairs of combinatorial optimization
problems that are linked by gauge duality. For example, the literature has
both time-honored [20] and more recent [6] publications leveraging the fact
that the stability number and the fractional chromatic number of a graph
define gauges dual to each other. Specially in cases where an approximation
algorithm rounds a solution to a convex relaxation of a combinatorial problem,
the (gauge) dual combinatorial problem may be approximated utilizing the ideas
within this work. On a broader note, it seems interesting to look for further
pair of problems which can be “simultaneously approximated”. Definition 12
provides a convenient formalization of simultaneous approximation for this
work, but even within the maximum cut and fractional cut-covering context
there are potentially sensible alternative definitions, as mentioned in Remark
13.

## References

  * [1] Noga Alon and Benny Sudakov  “Bipartite subgraphs and the smallest eigenvalue”  In _Combin. Probab. Comput._ 9.1, 2000, pp. 1–12  DOI: 10.1017/S0963548399004071
  * [2] A.. Aravkin, J.. Burke, D. Drusvyatskiy, M.. Friedlander and K.. MacPhee  “Foundations of gauge and perspective duality”  In _SIAM J. Optim._ 28.3, 2018, pp. 2406–2434  DOI: 10.1137/17M1119020
  * [3] Per Austrin, Siavosh Benabbas and Konstantinos Georgiou  “Better balance by being biased: a 0.8776-approximation for Max Bisection”  In _ACM Trans. Algorithms_ 13.1, 2016, pp. Art. 227  DOI: 10.1145/2907052
  * [4] Adi Avidor and Uri Zwick  “Rounding two and three dimensional solutions of the SDP relaxation of MAX CUT”  In _International Workshop on Approximation Algorithms for Combinatorial Optimization_ , 2005, pp. 14–25  Springer
  * [5] Nathan Benedetto Proença  “Combinatorial and geometric dualities in graph homomorphism optimization problems”, 2021  DOI: 10.11606/D.45.2021.tde-23092021-183204
  * [6] Nathan Benedetto Proença, Marcel K. Carli Silva and Gabriel Coutinho  “Dual Hoffman bounds for the stability and chromatic numbers based on semidefinite programming”  In _SIAM J. Discrete Math._ 35.4, 2021, pp. 2880–2907  DOI: 10.1137/19M1306427
  * [7] Lenore Blum, Felipe Cucker, Michael Shub and Steve Smale  “Complexity and Real Computation”  New York, NY: Springer, 1998
  * [8] Marcel K. Carli Silva and Levent Tunçel  “Optimization problems over unit-distance representations of graphs”  In _Electron. J. Combin._ 20.1, 2013, pp. Paper 4320pp  DOI: 10.37236/3128
  * [9] Marcel K. Carli Silva and Levent Tunçel  “Vertices of spectrahedra arising from the elliptope, the theta body, and their relatives”  In _SIAM J. Optim._ 25.1, 2015, pp. 295–316  DOI: 10.1137/130945818
  * [10] Etienne de Klerk and Frank Vallentin  “On the Turing model complexity of interior point methods for semidefinite programming”  In _SIAM J. Optim._ 26.3, 2016, pp. 1944–1961
  * [11] C. Delorme and S. Poljak  “Laplacian eigenvalues and the maximum cut problem”  In _Math. Programming_ 62.3, Ser. A, 1993, pp. 557–574  DOI: 10.1007/BF01585184
  * [12] Matt DeVos, Jaroslav Nešetřil and André Raspaud  “On edge-maps whose inverse preserves flows or tensions”  In _Graph theory in Paris_ , Trends Math.  Birkhäuser, Basel, 2007, pp. 109–138  DOI: 10.1007/978-3-7643-7400-6\\_10
  * [13] Uriel Feige and Gideon Schechtman  “On the optimality of the random hyperplane rounding technique for MAX CUT”  In _Random Structures & Algorithms_ 20.3, 2002, pp. 403–440  DOI: 10.1002/rsa.10036
  * [14] Robert M. Freund  “Dual gauge programs, with applications to quadratic programming and the minimum-norm problem”  In _Math. Programming_ 38.1, 1987, pp. 47–67  DOI: 10.1007/BF02591851
  * [15] Michael P. Friedlander, Ives Macêdo and Ting Kei Pong  “Gauge optimization and duality”  In _SIAM J. Optim._ 24.4, 2014, pp. 1999–2022  DOI: 10.1137/130940785
  * [16] D.. Fulkerson  “Anti-blocking polyhedra”  In _J. Combinatorial Theory Ser. B_ 12, 1972, pp. 50–71  DOI: 10.1016/0095-8956(72)90032-9
  * [17] D.. Fulkerson  “Blocking and anti-blocking pairs of polyhedra”  In _Math. Programming_ 1, 1971, pp. 168–194  DOI: 10.1007/BF01584085
  * [18] Chris Godsil and Gordon Royle  “Algebraic graph theory” 207, Graduate Texts in Mathematics  Springer-Verlag, New York, 2001  DOI: 10.1007/978-1-4613-0163-9
  * [19] Michel X. Goemans and David P. Williamson  “Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming”  In _J. ACM_ 42.6, 1995, pp. 1115–1145  DOI: 10.1145/227683.227684
  * [20] M. Grötschel, L. Lovász and A. Schrijver  “Relaxations of vertex packing”  In _J. Combinatorial Theory Ser. B_ 40.3, 1986, pp. 330–343  DOI: 10.1016/0095-8956(86)90087-0
  * [21] M. Grötschel, L. Lovász and A. Schrijver  “The ellipsoid method and its consequences in combinatorial optimization”  In _Combinatorica_ 1.2, 1981, pp. 169–197  DOI: 10.1007/BF02579273
  * [22] M. Grötschel and W.. Pulleyblank  “Weakly bipartite graphs and the max-cut problem”  In _Oper. Res. Lett._ 1.1, 1981, pp. 23–27  DOI: 10.1016/0167-6377(81)90020-1
  * [23] Samuel B. Hopkins, Tselil Schramm and Luca Trevisan  “Subexponential LPs approximate Max-Cut”  In _2020 IEEE 61st Annual Symposium on Foundations of Computer Science_ IEEE Computer Soc., Los Alamitos, CA, 2020, pp. 943–953  DOI: 10.1109/FOCS46700.2020.00092
  * [24] David Karger, Rajeev Motwani and Madhu Sudan  “Approximate graph coloring by semidefinite programming”  In _J. ACM_ 45.2, 1998, pp. 246–265  DOI: 10.1145/274787.274791
  * [25] Howard Karloff  “How good is the Goemans-Williamson MAX CUT algorithm?”  In _SIAM J. Comput._ 29.1, 1999, pp. 336–350  DOI: 10.1137/S0097539797321481
  * [26] Richard M. Karp  “Reducibility among combinatorial problems”  In _Complexity of computer computations (Proc. Sympos., IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y., 1972)_ Plenum, New York, 1972, pp. 85–103
  * [27] Subhash Khot, Guy Kindler, Elchanan Mossel and Ryan O’Donnell  “Optimal inapproximability results for MAX-CUT and other 2-variable CSPs?”  In _SIAM J. Comput._ 37.1, 2007, pp. 319–357  DOI: 10.1137/S0097539705447372
  * [28] Monique Laurent, Svatopluk Poljak and Franz Rendl  “Connections between semidefinite relaxations of the max-cut and stable set problems” Semidefinite programming  In _Math. Programming_ 77.2, Ser. B, 1997, pp. 225–246  DOI: 10.1016/S0025-5610(96)00084-6
  * [29] L. Lovász  “Graphs and Geometry”, Colloquium Publications  American Mathematical Society, 2019
  * [30] L. Lovász  “Semidefinite programs and combinatorial optimization”  In _Recent advances in algorithms and combinatorics_ 11, CMS Books Math./Ouvrages Math. SMC  Springer, New York, 2003, pp. 137–194  DOI: 10.1007/0-387-22444-0\\_6
  * [31] László Lovász  “On the Shannon capacity of a graph”  In _IEEE Trans. Inform. Theory_ 25.1, 1979, pp. 1–7  DOI: 10.1109/TIT.1979.1055985
  * [32] Sanjeev Mahajan and H. Ramesh  “Derandomizing approximation algorithms based on semidefinite programming”  In _SIAM J. Comput._ 28.5, 1999, pp. 1641–1663  DOI: 10.1137/S0097539796309326
  * [33] R.. McEliece, E.. Rodemich and H.. Rumsey  “The Lovász bound and some generalizations”  In _Journal of Combinatorics, Information & System Sciences_ 3.3, 1978, pp. 134–152
  * [34] Arkadi Nemirovski  “Introduction to Linear Optimization”, 2012  URL: https://www2.isye.gatech.edu/~nemirovs/OPTI_LectureNotes.pdf
  * [35] Yu. Nesterov  “Semidefinite relaxation and nonconvex quadratic optimization”  In _Optim. Methods Softw._ 9.1-3, 1998, pp. 141–160  DOI: 10.1080/10556789808805690
  * [36] José Neto and Walid Ben-Ameur  “On fractional cut covers”  In _Discrete Appl. Math._ 265, 2019, pp. 168–181  DOI: 10.1016/j.dam.2019.03.020
  * [37] Svatopluk Poljak and Franz Rendl  “Nonpolyhedral relaxations of graph-bisection problems”  In _SIAM J. Optim._ 5.3, 1995, pp. 467–487  DOI: 10.1137/0805024
  * [38] Robert Šámal  “Cubical coloring—fractional covering by cuts and semidefinite programming”  In _Discrete Math. Theor. Comput. Sci._ 17.2, 2015, pp. 251–266
  * [39] Robert Šámal  “On $XY$ Mappings”, 2006  URL: https://dspace.cuni.cz/handle/20.500.11956/6160
  * [40] A. Schrijver  “A comparison of the Delsarte and Lovász bounds”  In _Institute of Electrical and Electronics Engineers. Transactions on Information Theory_ 25.4, 1979, pp. 425–429  DOI: 10.1109/TIT.1979.1056072
  * [41] Luca Trevisan  “Max cut and the smallest eigenvalue”  In _SIAM J. Comput._ 41.6, 2012, pp. 1769–1786  DOI: 10.1137/090773714
  * [42] L. Tunçel  “Polyhedral and semidefinite programming methods in combinatorial optimization” 27, Fields Institute Monographs  Providence, RI: American Mathematical Society, 2010

##  Appendix A Edges with Arbitrarily Small Probability of being Covered

######  Proposition 31.

Let $\varepsilon\in(0,2)$. Set $G\coloneqq K_{3}$, set
$\beta\coloneqq{4}/{(4-\varepsilon)^{2}}$, and set

(97a) $\displaystyle w$
$\displaystyle\coloneqq(2-\varepsilon)\beta(e_{12}+e_{13})+\beta
e_{23}\in\mathbb{R}_{+}^{E(G)},$ (97b) $\displaystyle z$
$\displaystyle\coloneqq e_{12}+e_{13}+\varepsilon
e_{23}\in\mathbb{R}_{+}^{E(G)}.$

Then

(98) $(1,\bar{x})\text{ and }(\bar{\mu},\bar{Y})\text{ witness the membership
}(w,z)\in\mathrm{H}(G),$

where

$\bar{x}\coloneqq\frac{1}{4-\varepsilon}((2-\varepsilon)e_{1}+e_{2}+e_{3}),\quad\bar{\mu}\coloneqq\frac{4}{4-\varepsilon},\quad\text{and}\quad\bar{Y}\coloneqq\bar{\mu}\begin{bmatrix}1&\varepsilon/2-1&\varepsilon/2-1\\\
\varepsilon/2-1&1&1-2\varepsilon+\varepsilon^{2}/2\\\
\varepsilon/2-1&1-2\varepsilon+\varepsilon^{2}/2&1\end{bmatrix}.$

In particular, $(\bar{\mu},\bar{Y})$ is an optimal solution for the SDP 11.

###### Proof.

It is immediate that $\operatorname{diag}(\bar{Y})=\bar{\mu}\mathbbm{1}$. The
direct computation

$\frac{(4-\varepsilon)}{4}\bar{Y}=\begin{bmatrix}1\\\ \varepsilon/2-1\\\
\varepsilon/2-1\end{bmatrix}\begin{bmatrix}1&\varepsilon/2-1&\varepsilon/2-1\end{bmatrix}+(\varepsilon-\varepsilon^{2}/4)\begin{bmatrix}0\\\
1\\\ -1\end{bmatrix}\begin{bmatrix}0&1&-1\end{bmatrix}$

shows that $\bar{Y}\in\mathbb{S}_{+}^{V}$. Moreover, from 12 we get that

$\big{(}\tfrac{1}{4}\mathcal{L}_{G}^{*}(\bar{Y})\big{)}_{13}=\big{(}\tfrac{1}{4}\mathcal{L}_{G}^{*}(\bar{Y})\big{)}_{12}=\frac{2}{4-\varepsilon}-\frac{\varepsilon-2}{4-\varepsilon}=1=z_{12}=z_{13}.$

Furthermore

$\big{(}\tfrac{1}{4}\mathcal{L}_{G}^{*}(\bar{Y})\big{)}_{23}=\frac{2}{4-\varepsilon}-\frac{2(1-2\varepsilon+\varepsilon^{2}/2)}{4-\varepsilon}=\frac{4\varepsilon-\varepsilon^{2}}{4-\varepsilon}=\varepsilon=z_{23}.$

Thus, $(\bar{\mu},\bar{Y})$ is feasible in 11 for $(G,z)$. Set
$u\coloneqq(2-\varepsilon)e_{1}+e_{2}+e_{3}$. Moreover

$\displaystyle\tfrac{1}{4}\mathcal{L}_{G}(w)$
$\displaystyle=\tfrac{1}{4}(2-\varepsilon)\beta\mathcal{L}_{G}(e_{12}+e_{13})+\tfrac{1}{4}\beta\mathcal{L}_{G}(e_{23})$
by 97a
$\displaystyle=\tfrac{1}{4}\beta\Bigg{(}(2-\varepsilon)\begin{bmatrix}\phantom{-}2&-1&-1\\\
-1&\phantom{-}1&\phantom{-}0\\\
-1&\phantom{-}0&\phantom{-}1\end{bmatrix}+\begin{bmatrix}0&\phantom{-}0&\phantom{-}0\\\
0&\phantom{-}1&-1\\\ 0&-1&\phantom{-}1\end{bmatrix}\Bigg{)}$
$\displaystyle=\tfrac{1}{4}\beta\begin{bmatrix}4-2\varepsilon&\varepsilon-2&\varepsilon-2\\\
\varepsilon-2&3-\varepsilon&-1\\\ \varepsilon-2&-1&3-\varepsilon\end{bmatrix}$
$\displaystyle=\tfrac{1}{4}\beta\Bigg{(}(4-\varepsilon)\begin{bmatrix}2-\varepsilon&0&0\\\
0&1&0\\\
0&0&1\end{bmatrix}-\begin{bmatrix}(2-\varepsilon)^{2}&2-\varepsilon&2-\varepsilon\\\
2-\varepsilon&1&1\\\ 2-\varepsilon&1&1\end{bmatrix}\Bigg{)}$
$\displaystyle=\tfrac{1}{4}\beta\big{(}(4-\varepsilon)\operatorname{Diag}(u)-uu^{\mathsf{T}}\big{)}.$
by the definition of $u$
$\displaystyle\preceq\tfrac{1}{4}\beta(4-\varepsilon)\operatorname{Diag}(u)$
$\displaystyle=\operatorname{Diag}(\bar{x})$ $\displaystyle\text{since
$4\bar{x}=\beta(4-\varepsilon)u$}.$

Thus $(1,\bar{x})$ is feasible in 4b for $(G,w)$ as
$\mathbbm{1}^{\mathsf{T}}\bar{x}=1$. Since

$w^{\mathsf{T}}z=2(2-\varepsilon)\beta+\varepsilon\beta=\beta(4-\varepsilon)=\frac{4}{4-\varepsilon}=\bar{\mu},$

we obtain 98 from 47. Note that since $(1,\bar{x})$ is feasible in 4b, then
$(w,\bar{x})$ is feasible in 26b. Since 11 and 26b form a primal-dual pair of
SDPs, $\bar{\mu}=w^{\mathsf{T}}z$ implies optimality of $(\bar{\mu},\bar{Y})$
in 11. ∎

##  Appendix B SDP Solutions Defining Fractional Cut Covers with Exponential
Support

Theorem 32 below presents a rigorous statement and proof regarding 85, i.e.,
about the exponential support of a fractional cut cover derived from
Proposition 1.

######  Theorem 32.

Let $n\geq 3$ be an integer. Set $\bar{Y}\coloneqq
2I-\tfrac{2}{n}\mathbbm{1}\mathbbm{1}^{\mathsf{T}}$. For every $i\in[n]$, let
$g_{i}$ be independently sampled from the standard normal distribution, and
set $h\coloneqq\|g\|^{-1}g$. Then, for each nonempty $S\subsetneq V$,

$\mathbb{P}\big{(}\operatorname{GW}(\bar{Y},h)=S\big{)}>0$

###### Proof.

Let $S\subsetneq V$ be nonempty. Set

$\beta\coloneqq\min\bigg{\\{}\frac{2n-|S|-1}{|S|-1},\frac{n+|S|-1}{n-|S|-1}\bigg{\\}},$

where we consider $1/0$ to be $+\infty$. It is straightforward to check that
$\beta>1$. For each $v\in V$, let $A_{v}$ be the event that $1<g_{v}<\beta$
and let $B_{v}$ be the event that $-\beta<g_{v}<-1$. Since $g_{v}$ is sampled
from the standard normal distribution, we have that
$\mathbb{P}(A_{v})=\mathbb{P}(B_{v})\eqqcolon p$ is a positive constant
depending only on $\beta$.

Set

$D\coloneqq\bigg{(}\bigcap_{s\in S}A_{s}\bigg{)}\cap\bigg{(}\bigcap_{t\in
V\setminus S}B_{t}\bigg{)}.$

Note that, by the independence of $(g_{v})_{v\in V}$, we have that
$\mathbb{P}(D)=p^{n}>0$. We complete the proof by showing that $D$ implies
that

(99) $\operatorname{GW}(\bar{Y},h)=S.$

We will use the fact that the sampled shore is

(100) $\begin{split}\operatorname{GW}(\bar{Y},h)&=\\{\,{i\in
V}\,\colon{e_{i}^{\mathsf{T}}\bar{Y}^{\nicefrac{{1}}{{2}}}h\geq
0}\\}=\\{\,{i\in
V}\,\colon{e_{i}^{\mathsf{T}}(I-\tfrac{1}{n}\mathbbm{1}\mathbbm{1}^{\mathsf{T}})h\geq
0}\\}\\\ &=\Big{\\{}\,{i\in
V}\,\colon{h_{i}\geq\frac{\mathbbm{1}^{\mathsf{T}}h}{n}}\Big{\\}}=\Big{\\{}\,{i\in
V}\,\colon{g_{i}\geq\frac{\mathbbm{1}^{\mathsf{T}}g}{n}}\Big{\\}}\\\
&=\Big{\\{}\,{i\in V}\,\colon{(n-1)g_{i}\geq\sum_{v\in
V\setminus\\{i\\}}g_{v}}\Big{\\}},\end{split}$

Assume that $D$ holds. We first prove ‘$\supseteq$’ in 99. Let $s\in S$. Then

$\frac{1}{n-1}\sum_{v\in
V\setminus\\{s\\}}g_{v}=\frac{1}{n-1}\bigg{(}\sum_{s^{\prime}\in
S\setminus\\{s\\}}g_{s^{\prime}}+\sum_{t\in V\setminus
S}g_{t}\bigg{)}<\frac{1}{n-1}\left(\beta(|S|-1)-(n-|S|)\right)\leq 1<g_{s},$

since our choice of $\beta$ ensures that $\beta(|S|-1)\leq 2n-|S|-1$. Hence,
$s\in\operatorname{GW}(Y^{*},h)$ by 100.

We now prove ‘$\subseteq$’ in 99. Let $t\in V\setminus S$. Then

$\frac{1}{n-1}\sum_{v\in
V\setminus\\{t\\}}g_{v}=\frac{1}{n-1}\bigg{(}\sum_{t^{\prime}\in
V\setminus(S\cup\\{t\\})}g_{t^{\prime}}+\sum_{s\in
S}g_{s}\bigg{)}>\frac{1}{n-1}\left(-\beta(n-|S|-1)+|S|\right)\geq-1>g_{t},$

since our choice of $\beta$ ensures that $\beta(n-|S|-1)\leq n+|S|-1$. Thus,
$t\notin\operatorname{GW}(Y^{*},h)$ by 100. ∎

##  Appendix C SDP Solvers

In this section, we analyze the running time of an interior-point method (IPM)
to solve the SDP 58b to near optimality:

(58b)
$\eta_{\varepsilon}^{\circ}(G,z)=\min\\{\,{\mu}\,\colon{\mu\in\mathbb{R}_{+},\,Y\in\mathbb{S}^{V},\,Y\succeq\mu\varepsilon
I,\,\tfrac{1}{4}\mathcal{L}_{G}^{*}(Y)\geq
z,\,\operatorname{diag}(Y)=\mu\mathbbm{1}}\\}.$

Algorithms 1 and 4 in Theorems 6 and 24, resp., rely on obtaining such nearly
optimal solutions for 58b, where the parameter $\varepsilon$ lies in $[0,1)$.

For the purposes of stating the running time of IPMs, we will consider an
arbitrary primal SDP in the format

(101a) Minimize $\displaystyle\langle c,x\rangle$ (101b) subject to
$\displaystyle\mathcal{A}(x)\succeq_{\mathbb{L}^{*}}b,$ (101c) $\displaystyle
x\in\mathbb{K},$

and its (syntactically symmetric) dual,

(102a) Maximize $\displaystyle\langle b,y\rangle$ (102b) subject to
$\displaystyle y\in\mathbb{L},$ (102c)
$\displaystyle\mathcal{A}^{*}(y)\preceq_{\mathbb{K}^{*}}c,$

where

(103a) $\displaystyle\mathbb{K}$
$\displaystyle\coloneqq\mathbb{S}_{+}^{n_{1}}\oplus\mathbb{R}_{+}^{n_{2}}\oplus\mathbb{R}^{n_{3}}$
$\displaystyle\subseteq\mathbb{S}^{n_{1}}\oplus\mathbb{R}^{n_{2}}\oplus\mathbb{R}^{n_{3}}$
$\displaystyle\eqqcolon\mathbb{X}$ and (103b) $\displaystyle\mathbb{L}$
$\displaystyle\coloneqq\mathbb{S}_{+}^{m_{1}}\oplus\mathbb{R}_{+}^{m_{2}}\oplus\mathbb{R}^{m_{3}}$
$\displaystyle\subseteq\mathbb{S}^{m_{1}}\oplus\mathbb{R}^{m_{2}}\oplus\mathbb{R}^{m_{3}}$
$\displaystyle\eqqcolon\mathbb{Y}$

for some integers $n_{1},n_{2},n_{3},m_{1},m_{2},m_{3}\in\mathbb{N}$, the map
$\mathcal{A}\colon\mathbb{X}\to\mathbb{Y}$ is linear, $b\in\mathbb{Y}$, and
$c\in\mathbb{X}$. Here, the _dual cone_ of a cone $C$ in Euclidean space
$\mathbb{E}$ is $C^{*}\coloneqq\\{\,{y\in\mathbb{E}}\,\colon{\forall x\in
C,\,\langle y,x\rangle\geq 0}\\}$, and each of the notations $a\succeq_{C}b$
and $b\preceq_{C}a$, with $a,b\in\mathbb{E}$, means that $a-b\in C$.

Note that 101c and 103a allow for variables composed of positive semidefinite
matrices, nonnegative vectors, and free scalar variables. Similarly, 101b and
103b enables one to require affine functions of the variables to be positive
semidefinite, nonnegative, or _equal_ to zero. As an example, the SDP 58b can
be cast in the format 101 by setting

$\displaystyle\mathbb{K}\coloneqq\mathbb{S}_{+}^{0}\oplus\mathbb{R}_{+}^{1}\oplus\mathbb{S}^{V},\qquad\mathbb{L}\coloneqq\mathbb{S}_{+}^{V}\oplus\mathbb{R}_{+}^{E}\oplus\mathbb{R}^{V},$
$\displaystyle\mathcal{A}\colon\mu\oplus
Y\in\mathbb{R}^{1}\oplus\mathbb{S}^{V}\mapsto(Y-\mu\varepsilon
I)\oplus\big{(}\tfrac{1}{4}\mathcal{L}_{G}^{*}(Y)\big{)}\oplus\big{(}\mu\mathbbm{1}-\operatorname{diag}(Y)\big{)},$
$\displaystyle b\coloneqq 0\oplus z\oplus 0,\qquad c\coloneqq 1\oplus 0.$

Some IPMs proceed by producing a sequence of iterates tracking the so-called
central path. We will encode the procedure that updates an iterate to the next
one by a function $\Xi$, so that from an iterate $(x_{t},y_{t})$ of primal-
dual solutions, the next iterate will be
$\Xi(x_{t},y_{t})\eqqcolon(x_{t+1},y_{t+1})$.

The number of iterations of IPMs so that the duality gap for a pair of
solutions $(x_{t},y_{t})$ is a $\delta$-fraction of the inital duality gap can
be bounded by a function $\psi$ on the initial Slater points
$(x_{0},y_{0})\coloneqq(\mathring{x},\mathring{y})$. Set

(104) $N\coloneqq n_{1}+n_{2}+m_{1}+m_{2}.$

For each pair $(x,y)$ of primal-dual feasible solutions, where

$\displaystyle x$ $\displaystyle\eqqcolon X_{1}$ $\displaystyle\oplus x_{2}$
$\displaystyle\oplus x_{3}$ $\displaystyle\in\mathbb{X},$ $\displaystyle y$
$\displaystyle\eqqcolon Y_{1}$ $\displaystyle\oplus y_{2}$
$\displaystyle\oplus y_{3}$ $\displaystyle\in\mathbb{Y},$ and with
corresponding slacks $\displaystyle\mathcal{A}(x)-b$ $\displaystyle\eqqcolon
U_{1}$ $\displaystyle\oplus u_{2}$ $\displaystyle\oplus u_{3}$
$\displaystyle\in\mathbb{Y},$ $\displaystyle c-\mathcal{A}^{*}(y)$
$\displaystyle\eqqcolon V_{1}$ $\displaystyle\oplus v_{2}$
$\displaystyle\oplus v_{3}$ $\displaystyle\in\mathbb{X},$

define

(105) $\psi(x,y)\coloneqq N\ln\bigg{(}\frac{1}{N}\Big{\langle}X_{1}\oplus
x_{2}\oplus Y_{1}\oplus y_{2},V_{1}\oplus v_{2}\oplus U_{1}\oplus
u_{2}\Big{\rangle}\bigg{)}\\\
-\ln\bigg{(}\det(X_{1})\det(V_{1})\det(Y_{1})\det(U_{1})\Big{(}\prod
x_{2}\Big{)}\Big{(}\prod v_{2}\Big{)}\Big{(}\prod y_{2}\Big{)}\Big{(}\prod
u_{2}\Big{)}\bigg{)},$

where, for each vector $a$, we denote $\prod
a\coloneqq\det(\operatorname{Diag}(a))$. The function $\psi$ takes into
account two important factors that affect the number of required iterations:
the first term in the RHS of 105 depends on the initial duality gap
$\big{\langle}X_{1}\oplus x_{2}\oplus Y_{1}\oplus y_{2},V_{1}\oplus
v_{2}\oplus U_{1}\oplus u_{2}\big{\rangle},$ whereas the second term is
related to the centrality of the initial Slater point. Indeed, it is intuitive
that in IPMs, a good initial point should have a reasonably good duality gap
and at the same time not being too close to the boundary of the feasible
region.

The next result is adapted from [42, Theorem 4.5] for our format of SDPs:

######  Theorem 33.

Let $\delta\in(0,1)$ and let $(x_{0},y_{0})$ be a primal-dual pair of feasible
solutions for 101 and 102, respectively, such that

$\psi(x_{0},y_{0})\leq\sqrt{N}\ln\left(1/\delta\right),$

where $N$ is defined as in 104 and $\psi$ as in 105. Define the sequence
$(x_{t},y_{t})_{t=0}^{\infty}$ by $(x_{t+1},y_{t+1})\coloneqq\Xi(x_{t},y_{t})$
for each $t\in\mathbb{N}$. Define the sequence $(u_{t},v_{t})_{t=0}^{\infty}$
by $u_{t}\coloneqq\mathcal{A}(x_{t})-b$ and $v_{t}\coloneqq
c-\mathcal{A}^{*}(y_{t})$ for each $t\in\mathbb{N}$. Then

$\langle x_{t}\oplus u_{t},v_{t}\oplus y_{t}\rangle\leq\delta\langle
x_{0}\oplus u_{0},v_{0}\oplus y_{0}\rangle\qquad\text{for each
}t\geq\bar{t}\coloneqq 24\sqrt{N}\ln(1/\delta).$

######  Proposition 34.

Let $\sigma\in(0,2/3)$. There exists a polynomial-time algorithm that, given a
graph $G=(V,E)$ with $n$ vertices and $m$ edges, a nonzero vector
$z\in\mathbb{R}_{+}^{E}$, and a number $\varepsilon\in[0,1/3]$, computes
feasible solutions $(x,w)$ for 58a and $(\mu,Y)$ for 58b such that $\mu\leq
z^{\mathsf{T}}w+\sigma\|z\|_{\infty}$. The algorithm consists of applying an
interior-point method for $T\coloneqq 24(n+m+1)\ln(8/\sigma)$ iterations; each
iteration encoding one application of the function $\Xi$ can be made to run in
time $O((n+m)^{3})$.

######  Remark.

Note that, since $\sigma$ is constant, the SDPs 58 can be nearly solved (in
the sense of the $\sigma\|z\|_{\infty}$ additive error) in strongly polynomial
time.

###### Proof.

First we write 58b and its dual. We scale the cost function of 58b by
$N\coloneqq n+m+1$, and we normalize the edge weights by setting
$\bar{z}\coloneqq z/\|z\|_{\infty}$:

$\begin{array}[]{rrl}\textrm{(P)}&\inf&N\mu\\\\[2.0pt] &\text{subject
to}&Y-\mu\varepsilon I\succeq 0,\\\\[2.0pt]
&&\tfrac{1}{4}\mathcal{L}_{G}^{*}(Y)\geq\bar{z},\\\\[2.0pt]
&&-\operatorname{diag}(Y)+\mu\mathbbm{1}=0,\\\\[2.0pt]
&&Y\in\mathbb{S}^{V},\\\\[2.0pt]
&&\mu\in\mathbb{R}_{+},\end{array}\quad\begin{array}[]{rrl}\textrm{(D)}&\sup&\bar{z}^{\mathsf{T}}w\\\\[2.0pt]
&\text{subject to}&S\in\mathbb{S}_{+}^{V},\\\\[2.0pt]
&&w\in\mathbb{R}_{+}^{E},\\\\[2.0pt] &&x\in\mathbb{R}^{V},\\\\[2.0pt]
&&S+\tfrac{1}{4}\mathcal{L}_{G}(w)-\operatorname{Diag}(x)=0,\\\\[2.0pt]
&&\mathbbm{1}^{\mathsf{T}}x-\varepsilon\operatorname{Tr}(S)\leq N.\end{array}$

Set

$\displaystyle\mathring{\mu}\coloneqq 4,$ $\displaystyle\mathring{Y}\coloneqq
4I,$ $\displaystyle\mathring{w}\coloneqq\mathbbm{1},$
$\displaystyle\mathring{x}\coloneqq\tfrac{1}{2}\deg_{G}+\mathbbm{1},$
$\displaystyle\mathring{S}\coloneqq I+\tfrac{1}{4}D(G)+\tfrac{1}{4}A(G),$

where $D(G)\coloneqq\operatorname{Diag}(\deg_{G})$. It is straightforward to
check that $\mathring{Y}\oplus\mathring{\mu}$ and
$\mathring{S}\oplus\mathring{w}\oplus\mathring{x}$ are Slater points for (P)
and (D), resp., with corresponding slacks

$\displaystyle\mathring{U}$
$\displaystyle\coloneqq\mathring{Y}-\mathring{\mu}\varepsilon
I=4(1-\varepsilon)I,$ $\displaystyle\mathring{u}$
$\displaystyle\coloneqq\tfrac{1}{4}\mathcal{L}_{G}^{*}(\mathring{Y})-\bar{z}=2\mathbbm{1}-\bar{z},$
$\displaystyle\mathring{\nu}$ $\displaystyle\coloneqq
N-\mathbbm{1}^{\mathsf{T}}\mathring{x}+\varepsilon\operatorname{Tr}(\mathring{S})=1+\tfrac{\varepsilon}{2}m+\varepsilon
n.$

The duality gap between $\mathring{Y}\oplus\mathring{\mu}$ and
$\mathring{S}\oplus\mathring{w}\oplus\mathring{x}$ is

(106)
$\begin{split}\mathring{\mu}\mathring{\nu}+\langle\mathring{U},\mathring{S}\rangle+\mathring{u}^{\mathsf{T}}\mathring{w}&=4(1+\tfrac{\varepsilon}{2}m+\varepsilon
n)+4(1-\varepsilon)\operatorname{Tr}(I+\tfrac{1}{4}D(G)+\tfrac{1}{4}A(G))+2\mathbbm{1}^{\mathsf{T}}\mathbbm{1}-\mathbbm{1}^{\mathsf{T}}\bar{z}\\\
&\leq 4(1+\tfrac{\varepsilon}{2}m+\varepsilon n)+4n+4m\leq 4(1+m/2+n)+4n+4m\\\
&\leq 8(1+m+n)=8N.\end{split}$

We will now compute an upper bound for the value of the function $\psi$ for
$\mathring{Y}\oplus\mathring{\mu}$ and
$\mathring{S}\oplus\mathring{w}\oplus\mathring{x}$. Since we already computed
an upper bound for the duality gap in 106, we will now lower bound the
determinants:

$\mathring{\mu}\cdot\det(\mathring{U})\cdot\Big{(}\prod\mathring{u}\Big{)}\cdot\mathring{\nu}\cdot\det(\mathring{S})\cdot\Big{(}\prod\mathring{w}\Big{)}\\\
=4\cdot\det\big{(}4(1-\varepsilon)I\big{)}\cdot\prod(2\mathbbm{1}-\bar{z})\cdot(1+\tfrac{\varepsilon}{2}m+\varepsilon
n)\cdot\det\big{(}I+\tfrac{1}{4}D(G)+\tfrac{1}{4}A(G)\big{)}\cdot\prod\mathbbm{1}\\\
\geq 4\det\big{(}4(1-\varepsilon)I\big{)}\det(I)\geq
4^{n}(1-\varepsilon)^{n},$

where in the first inequality we used that $\|\bar{z}\|_{\infty}=1$ and
$I+\tfrac{1}{4}D(G)+\tfrac{1}{4}A(G)\succeq I$. Thus,

$\psi(\mathring{\mu}\oplus\mathring{Y},\mathring{S}\oplus\mathring{w}\oplus\mathring{x})\leq
N\ln\Big{(}\frac{1}{N}(8N)\Big{)}-\ln(4^{n}(1-\varepsilon)^{n})\leq N\ln(8).$

Set
$\delta\coloneqq(8/\sigma)^{\sqrt{N}}\leq\min\big{\\{}\sigma/8,8^{-\sqrt{N}}\big{\\}}$.
By Theorem 33, after $24\sqrt{N}\ln(1/\delta)=O(N)$ iterations of $\Xi$, the
duality gap is at most $8\delta N\leq\sigma N$. That is, we obtain
$\tilde{Y}\oplus\tilde{\mu}$ and $\tilde{S}\oplus\tilde{w}\oplus\tilde{x}$,
feasible for (P) and (D), resp., such that $N\tilde{\mu}\leq
N\bar{z}^{\mathsf{T}}\tilde{w}+N\sigma$, that is,
$\tilde{\mu}\leq\bar{z}^{\mathsf{T}}\tilde{w}+\sigma$. Hence,
$\|z\|_{\infty}\cdot(\tilde{Y}\oplus\tilde{\mu})$ is feasible for 58b with
objective value $\|z\|_{\infty}\tilde{\mu}\leq
z^{\mathsf{T}}\tilde{w}+\sigma\|z\|_{\infty}$. ∎