  The Densest $k$-Subgraph (D$k$S) problem, and its corresponding minimization
problem Smallest $p$-Edge Subgraph (S$p$ES), have come to play a central role
in approximation algorithms. This is due both to their practical importance,
and their usefulness as a tool for solving and establishing approximation
bounds for other problems. These two problems are not well understood, and it
is widely believed that they do not an admit a subpolynomial approximation
ratio (although the best known hardness results do not rule this out).
  In this paper we generalize both D$k$S and S$p$ES from graphs to hypergraphs.
We consider the Densest $k$-Subhypergraph problem (given a hypergraph $(V, E)$,
find a subset $W\subseteq V$ of $k$ vertices so as to maximize the number of
hyperedges contained in $W$) and define the Minimum $p$-Union problem (given a
hypergraph, choose $p$ of the hyperedges so as to minimize the number of
vertices in their union). We focus in particular on the case where all
hyperedges have size 3, as this is the simplest non-graph setting. For this
case we provide an $O(n^{4(4-\sqrt{3})/13 + \epsilon}) \leq
O(n^{0.697831+\epsilon})$-approximation (for arbitrary constant $\epsilon > 0$)
for Densest $k$-Subhypergraph and an $\tilde O(n^{2/5})$-approximation for
Minimum $p$-Union. We also give an $O(\sqrt{m})$-approximation for Minimum
$p$-Union in general hypergraphs. Finally, we examine the interesting special
case of interval hypergraphs (instances where the vertices are a subset of the
natural numbers and the hyperedges are intervals of the line) and prove that
both problems admit an exact polynomial time solution on these instances.
