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

Anand Louis, Yury Makarychev

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…