文章基本信息

标题：Approximation Algorithms for Hypergraph Small Set Expansion and Small Set Vertex Expansion
本地全文：下载
作者：Anand Louis ; Yury Makarychev
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2014
卷号：28
页码：339-355
DOI：10.4230/LIPIcs.APPROX-RANDOM.2014.339
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：The expansion of a hypergraph, a natural extension of the notion of expansion in graphs, is defined as the minimum over all cuts in the hypergraph of the ratio of the number of the hyperedges cut to the size of the smaller side of the cut. We study the Hypergraph Small Set Expansion problem, which, for a parameter 's' such that 0 < s < 1/2, asks to compute the cut having the least expansion while having at most 's' fraction of the vertices on the smaller side of the cut. We present two algorithms. Our first algorithm gives a multiplicative polylogarithmic approximation. Our second algorithm gives a bound that is a function of the expansion of the hypergraph but is independent of the size of the hypergraph. Using these results, we also obtain similar guarantees for the Small Set Vertex Expansion problem.
关键词：Approximation Algorithms; Graph Expansion; Hypergraph Expansion; Vertex Expansion