The container selection problem

We introduce and study a network resource management problem that is a special case of nonmetric k-median, naturally arising in cross platform scheduling and cloud computing. In the continuous d-dimensional container selection problem, we are given a set C ⊂ R^d of input points, for some d ≥ 2, and a budget k. An input point p can be assigned to a "container point" c only if c dominates p in every dimension. The assignment cost is then equal to the ell;1-norm of the container point. The goal is to find k container points in R^d, such that the total assignment cost for all input points is minimized. The discrete variant of the problem has one key distinction, namely, the container points must be chosen from a given set F of points. For the continuous version, we obtain a polynomial time approximation scheme for any fixed dimension d ≥ 2. On the negative side, we show that the problem is NP-hard for any d ≥ 3. We further show that the discrete version is significantly harder, as it is NP-hard to approximate without violating the budget k in any dimension d ≥ 3. Thus, we focus on obtaining bi-approximation algorithms. For d = 2, the bi-approximation guarantee is (1+ε, 3), i.e., for any ε > 0, our scheme outputs a solution of size 3k and cost at most (1 + ε) times the optimum. For fixed d > 2, we present a (1 + ε,O(1/ε log k)) bi-approximation algorithm.