English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

The expansion of a hypergraph, a natural extension of the notion of expansionin graphs, is defined as the minimum over all cuts in the hypergraph of theratio of the number of the hyperedges cut to the size of the smaller side ofthe cut. We study the Hypergraph Small Set Expansion problem, which, for aparameter $\delta \in (0,1/2]$, asks to compute the cut having the leastexpansion while having at most $\delta$ fraction of the vertices on the smallerside of the cut. We present two algorithms. Our first algorithm gives an$\tilde O(\delta^{-1} \sqrt{\log n})$ approximation. The second algorithm findsa set with expansion $\tilde O(\delta^{-1}(\sqrt{d_{\text{max}}r^{-1}\log r\,\phi^*} + \phi^*))$ in a $r$--uniform hypergraph with maximum degree$d_{\text{max}}$ (where $\phi^*$ is the expansion of the optimal solution).Using these results, we also obtain algorithms for the Small Set VertexExpansion problem: we get an $\tilde O(\delta^{-1} \sqrt{\log n})$approximation algorithm and an algorithm that finds a set with vertex expansion$O\left(\delta^{-1}\sqrt{\phi^V \log d_{\text{max}} } + \delta^{-1}\phi^V\right)$ (where $\phi^V$ is the vertex expansion of the optimalsolution).  For $\delta=1/2$, Hypergraph Small Set Expansion is equivalent to thehypergraph expansion problem. In this case, our approximation factor of$O(\sqrt{\log n})$ for expansion in hypergraphs matches the correspondingapproximation factor for expansion in graphs due to ARV.

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