Title: A Primal-Dual Extension of the Goemans--Williamson Algorithm for the Weighted Fractional Cut Covering Problem
| Speaker: | Nathan Benedetto Proenca |
| Affiliation: | University of Waterloo |
| Location: | MC 6029 |
Abstract:
A cut in a graph \(G = (V, E)\) is a set of edges which has precisely one endpoint in \(S\), for a given subset \(S\) of \(V\). The fractional cut-covering number is the optimal value of a linear programming relaxation for the problem of covering each edge by a set of cuts. We define a semidefinite programming relaxation of fractional cut covering whose approximate optimal solutions may be rounded into a fractional cut cover via a randomized algorithm. These results arise from the tight connection between fractional cut covering and the maximum cut problem. By pinpointing the fundamental aspects of this relationship via antiblocker and gauge duality, we are not only able to obtain dual results to the celebrated work of Goemans and Williamson, but also to tie both approximation constants, to obtain new optimality certificates, and to relate both problems to geometric representation of graphs. This is joint work with Marcel K. de Carli Silva, Cristiane Maria Sato, and Levent Tunçel.