The container selection problem

Viswanath Nagarajan, Kanthi K. Sarpatwar, Baruch Schieber, Hadas Shachnai, Joel L. Wolf

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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 ⊂ Rd 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 Rd, 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.

Original languageEnglish (US)
Title of host publicationApproximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 18th International Workshop, APPROX 2015, and 19th International Workshop, RANDOM 2015
EditorsNaveen Garg, Klaus Jansen, Anup Rao, Jose D. P. Rolim
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Pages416-434
Number of pages19
ISBN (Electronic)9783939897897
DOIs
StatePublished - Aug 1 2015
Externally publishedYes
Event18th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2015, and 19th International Workshop on Randomization and Computation, RANDOM 2015 - Princeton, United States
Duration: Aug 24 2015Aug 26 2015

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume40
ISSN (Print)1868-8969

Conference

Conference18th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2015, and 19th International Workshop on Randomization and Computation, RANDOM 2015
CountryUnited States
CityPrinceton
Period8/24/158/26/15

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Approximation algorithms
  • Cloud computing
  • Cross platform scheduling
  • Geometric hitting set
  • Non-metric k-median

Fingerprint Dive into the research topics of 'The container selection problem'. Together they form a unique fingerprint.

Cite this