A Primal-Dual Extension o
A Primal-Dual Extension of the Goemans–Williamson Algorithm for the Weighted Fractional Cut-Covering Problem
A Primal-Dual Extension of the Goemans–Williamson Algorithm for the Weighted Fractional Cut-Covering Problem
arXiv:2311.15346v2 Announce Type: replace-cross
Abstract: 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 who…
