Events items teaser

Algebraic Graph Theory - Nathan Benedetto Proenca
2023-04-24 11:30 (America/Toronto)
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.
