Key points are not available for this paper at this time.
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 Z^+, 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 S₁, , Sₘ that cover all the vertices, such that for any 1 j m, the total size of vertices in Sⱼ is bounded by k, and there are no edges from V Sⱼ to Sⱼ. 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 Z₀^+, and k Z^+. 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 w. r. t. 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 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.
Doron-Arad et al. (Sun,) studied this question.