  We study a weighted generalization of the fractional cut-covering problem,
which we relate to the maximum cut problem via antiblocker and gauge duality.
This relationship allows us to introduce a semidefinite programming (SDP)
relaxation whose solutions may be rounded into fractional cut covers by
sampling via the random hyperplane technique. We then provide a
$1/\alpha_{\scriptscriptstyle \mathrm{GW}}$-approximation algorithm for the
weighted fractional cut-covering problem, where $\alpha_{\scriptscriptstyle
\mathrm{GW}} \approx 0.878$ is the approximation factor of the celebrated
Goemans--Williamson algorithm for the maximum cut problem. Nearly optimal
solutions of the SDPs in our duality framework allow one to consider instances
of the maximum cut and the fractional cut-covering problems as primal-dual
pairs, where cuts and fractional cut covers simultaneously certify each other's
approximation quality. We exploit this relationship to introduce new
combinatorial certificates for both problems, as well as a randomized
polynomial-time algorithm for producing such certificates. In~particular,
we~show how the Goemans--Williamson algorithm implicitly approximates a
weighted instance of the fractional cut-covering problem, and how our new
algorithm explicitly approximates a weighted instance of the maximum cut
problem. We conclude by discussing the role played by geometric representations
of graphs in our results, and by proving our algorithms and analyses to be
optimal in several aspects.
