  Motivated by applications in production planning and storage allocation in
hierarchical databases, we initiate the study of covering partially ordered
items (CPO). Given a capacity $k \in \mathbb{Z}^+$, and a directed graph
$G=(V,E)$ where each vertex has a size in $\{0,1, \ldots,k\}$, we seek a
collection of subsets of vertices $S_1, \ldots, S_m$ that cover all the
vertices, such that for any $1 \leq j \leq m$, the total size of vertices in
$S_j$ is bounded by $k$, and there are no edges from $V \setminus S_j$ to
$S_j$. The objective is to minimize the number of subsets $m$. CPO is closely
related to the rule caching problem (RCP) that is of wide interest in the
networking area. The input for RCP is a directed graph $G=(V,E)$, a profit
function $p:V \rightarrow \mathbb{Z}_{0}^+$, and $k \in \mathbb{Z}^+$. The
output is a subset $S \subseteq V$ of maximum profit such that $|S| \leq k$ and
there are no edges from $V \setminus S$ to $S$.
  Our main result is a $2$-approximation algorithm for CPO on out-trees,
complemented by an asymptotic $1.5$-hardness of approximation result. We also
give a two-way reduction between RCP and the densest $k$-subhypergraph problem,
surprisingly showing that the problems are equivalent w.r.t. polynomial-time
approximation within any factor $\rho \geq 1$. This implies that RCP cannot be
approximated within factor $|V|^{1-\eps}$ for any fixed $\eps>0$, under
standard complexity assumptions. Prior to this work, RCP was just known to be
strongly NP-hard. We further show that there is no EPTAS for the special case
of RCP where the profits are uniform, assuming Gap-ETH. Since this variant
admits a PTAS, we essentially resolve the complexity status of this problem.
