  In the Minimum k-Union problem (MkU) we are given a set system with n sets
and are asked to select k sets in order to minimize the size of their union.
Despite being a very natural problem, it has received surprisingly little
attention: the only known approximation algorithm is an
$O(\sqrt{n})$-approximation due to [Chlamt\'a\v{c} et al APPROX '16]. This
problem can also be viewed as the bipartite version of the Small Set Vertex
Expansion problem (SSVE), which we call the Small Set Bipartite Vertex
Expansion problem (SSBVE). SSVE, in which we are asked to find a set of k nodes
to minimize their vertex expansion, has not been as well studied as its
edge-based counterpart Small Set Expansion (SSE), but has recently received
significant attention, e.g. [Louis-Makarychev APPROX '15]. However, due to the
connection to Unique Games and hardness of approximation the focus has mostly
been on sets of size $k = \Omega(n)$, while we focus on the case of general
$k$, for which no polylogarithmic approximation is known.
  We improve the upper bound for this problem by giving an
$n^{1/4+\varepsilon}$ approximation for SSBVE for any constant $\varepsilon >
0$. Our algorithm follows in the footsteps of Densest $k$-Subgraph (DkS) and
related problems, by designing a tight algorithm for random models, and then
extending it to give the same guarantee for arbitrary instances. Moreover, we
show that this is tight under plausible complexity conjectures: it cannot be
approximated better than $O(n^{1/4})$ assuming an extension of the so-called
"Dense vs Random" conjecture for DkS to hypergraphs. We show that the same
bound is also matched by an integrality gap for a super-constant number of
rounds of the Sherali-Adams LP hierarchy, and an even worse integrality gap for
the natural SDP relaxation. Finally, we design a simple bicriteria $\tilde
O(\sqrt{n})$ approximation for the more general SSVE problem.
