License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2014.339
URN: urn:nbn:de:0030-drops-47079
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2014/4707/
Go to the corresponding LIPIcs Volume Portal

Louis, Anand ; Makarychev, Yury

Approximation Algorithms for Hypergraph Small Set Expansion and Small Set Vertex Expansion

pdf-format:
24.pdf (0.5 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{louis_et_al:LIPIcs:2014:4707,
  author =	{Anand Louis and Yury Makarychev},
  title =	{{Approximation Algorithms for Hypergraph Small Set Expansion and Small Set Vertex Expansion}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)},
  pages =	{339--355},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-74-3},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{28},
  editor =	{Klaus Jansen and Jos{\'e} D. P. Rolim and Nikhil R. Devanur and Cristopher Moore},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2014/4707},
  URN =		{urn:nbn:de:0030-drops-47079},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2014.339},
  annote =	{Keywords: Approximation Algorithms, Graph Expansion, Hypergraph Expansion, Vertex Expansion}
}

Keywords: Approximation Algorithms, Graph Expansion, Hypergraph Expansion, Vertex Expansion
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)
Issue Date: 2014
Date of publication: 04.09.2014

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI