A Primal-Dual Extension of the Goemans--Williamson Algorithm for the Weighted Fractional Cut-Covering Problem

• Published in: arXiv.org 2023-11
• Main Authors: Nathan Benedetto Proença, Marcel K de Carli Silva, Sato, Cristiane M, Tunçel, Levent
• Format: Article
• Language: English
• Subjects: Algorithms; Approximation; Certificates; Combinatorial analysis; Graphical representations; Hyperplanes; Mathematical analysis; Polynomials; Semidefinite programming
• ISSN: 2331-8422

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.