Efficient Flow-based Approximation Algorithms for Submodular Hypergraph Partitioning via a Generalized Cut-Matching Game
share
In the past 20 years, increasing complexity in real world data has lead to the study of higher-order data models based on partitioning hypergraphs. However, hypergraph partitioning admits multiple formulations as hyperedges can be cut in multiple ways. Building upon a class of hypergraph partitioning problems introduced by Li Milenkovic, we study the problem of minimizing ratio-cut objectives over hypergraphs given by a new class of cut functions, monotone submodular cut functions (mscf's), which captures hypergraph expansion and conductance as special cases. We first define the ratio-cut improvement problem, a family of local relaxations of the minimum ratio-cut problem. This problem is a natural extension of the Andersen Lang cut improvement problem to the hypergraph setting. We demonstrate the existence of efficient algorithms for approximately solving this problem. These algorithms run in almost-linear time for the case of hypergraph expansion, and when the hypergraph rank is at most O(1). Next, we provide an efficient O(log n)-approximation algorithm for finding the minimum ratio-cut of G. We generalize the cut-matching game framework of Khandekar et. al. to allow for the cut player to play unbalanced cuts, and matching player to route approximate single-commodity flows. Using this framework, we bootstrap our algorithms for the ratio-cut improvement problem to obtain approximation algorithms for minimum ratio-cut problem for all mscf's. This also yields the first almost-linear time O(log n)-approximation algorithms for hypergraph expansion, and constant hypergraph rank. Finally, we extend a result of Louis Makarychev to a broader set of objective functions by giving a polynomial time O(√(log n))-approximation algorithm for the minimum ratio-cut problem based on rounding ℓ_2^2-metric embeddings.
READ FULL TEXT