Approximations and Hardness of Covering and Packing Partially Ordered Items

Motivated by applications in production planning and storage allocation in hierarchical databases, we initiate the study of covering partially ordered items (cpo). Given a value k∈N, and a directed graph G=(V,E) where each vertex has a size in {0,1,…,k}, we seek a collection of subsets of vertices C₁,…,C_t that cover all the vertices, such that for any 1≤j≤t, the total size of vertices in C_j is bounded by k, and there are no edges from V\C_j to C_j. The objective is to minimize the number of subsets t. cpo is closely related to the rule caching problem (rcp) that has been widely studied in the networking area. The input for rcp is a directed graph G=(V,E), a profit function p:V→Z₀⁺, and k∈N. The output is a subset S⊆V of maximum profit such that |S|≤k and there are no edges from V\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 with respect to polynomial-time approximation within any factor ρ≥1. This implies that rcp cannot be approximated within factor |V|^1-ε for any fixed ε>0, under standard complexity assumptions. Prior to this work, rcp was only 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.