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\big(\sqrt{\log n}\big)$-approximation algorithm for the minimum ratio-cut problem based on rounding $\ell_2^2$-metric embeddings.
翻译:在过去20年中,现实世界数据日益复杂,导致对基于分流超强的更高级数据模型进行研究。然而,高空分区会承认多种配方,因为高端可以以多种方式削减。根据李和米林科维奇提出的高端分区问题,我们研究如何在高空次式剪裁功能的新类别、单体亚式剪裁功能(mscf's)给出的高端数据模型中最大限度地减少比率目标的问题,该功能将超度比率扩大和行为率作为特例。我们首先定义了比率-下降比率比率的改善问题,即当地最低比率的降价比率。这是安得森和朗将改进问题与超度设置的自然延伸。我们展示了高效的算法来解决这一问题。这些算法在高度扩张的情况下几乎是直线式的,而高度级值排名则以美元为最高值。我们首先将高效的美元比值-平价比率的递减率值-平比值比值 将我们最短的比值比值的比值比值比值比值比值的比值推算算成了美元。