Events by date

Title: A Primal-Dual Extension of the Goemans and Williamson Algorithm for Weighted Fractional Cut Cover

Speaker: Nathan Benedetto Proenca Affiliation: University of Waterloo Location: Please contact Sabrina Lato for Zoom link

Abstract: A cut in a graph G = (V, E) is a set of edges which has 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. Beyond its role as part of Šámal's work on cut continuous functions, this graph parameter also arises as the gauge dual of the maximum cut problem.