3 papers
Maximum Cuts and Fractional Cut Covers: A Computational Study of a Randomized Semidefinite Programming Approach
Nathan Benedetto Proença, Marcel K. de Carli Silva, Cristiane M. Sato +1
We present experimental work on a primal-dual framework simultaneously approximating maximum cut and weighted fractional cut-covering instances. In this primal-dual framework, we s…
A Primal-Dual Extension of the Goemans--Williamson Algorithm for the Weighted Fractional Cut-Covering Problem
Nathan Benedetto Proença, Marcel K. de Carli Silva, Cristiane M. Sato +1
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…
Generalized Cuts and Grothendieck Covers: a Primal-Dual Approximation Framework Extending the Goemans--Williamson Algorithm
Nathan Benedetto Proença, Marcel K. de Carli Silva, Cristiane M. Sato +1
We provide a primal-dual framework for randomized approximation algorithms utilizing semidefinite programming (SDP) relaxations. Our framework pairs a continuum of APX-complete pro…