Antares Chen, University of Chicago
Last time, we discussed a non-linear and non-differentiable Laplacian operator for hypergraphs in which aspects of spectral graph theory still generalize to the hypergraph setting. Building on these tools, we discuss a primal-dual approximation algorithm for a specific class of hypergraph partitioning problems called “minimum ratio-cut”. To do this, we construct a family of local, convex relaxations of the minimum ratio-cut problem, and compose dual solutions using “cut-matching games” to certify lower bounds on the minimum ratio-cut objective. This approach leads to the first $O(\log n)$-approximation for hypergraph sparsest cut that runs in almost-linear time.
Joint work with Konstantinos Ameranis, Lorenzo Orecchia, and Erasmo Tani.
Join via Zoom