A primal-dual extension of the Goemans-Williamson algorithm for the weighted fractional cut-covering problem

• 成果类型: Article; Early Access
• 署名作者: Proenca, Nathan Benedetto; Silva, Marcel K. de Carli; Sato, Cristiane M.; Tuncel, Levent
• 署名单位: University of Waterloo; Universidade de Sao Paulo; Universidade Federal do ABC (UFABC)
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-025-02209-0
• 发表日期: 2025
• 关键词: max-cut; Approximation algorithms; maximum cut; semidefinite; gauge; relaxations; complexity

摘要

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 GW\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$1/\alpha _{\scriptscriptstyle \textrm{GW}}$$\end{document}-approximation algorithm for the weighted fractional cut-covering problem, where alpha GW approximate to 0.878\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\alpha _{\scriptscriptstyle \textrm{GW}}\approx 0.878$$\end{document} 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.