Nagarajan, Viswanath ;
Sarpatwar, Kanthi K. ;
Schieber, Baruch ;
Shachnai, Hadas ;
Wolf, Joel L.
The Container Selection Problem
Abstract
We introduce and study a network resource management problem that is a special case of nonmetric kmedian, naturally arising in cross platform scheduling and cloud computing. In the continuous ddimensional container selection problem, we are given a set C of input points in ddimensional Euclidean space, 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 L1norm of the container point. The goal is to find k container points in the ddimensional space, 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 NPhard for any d>=3. We further show that the discrete version is significantly harder, as it is NPhard to approximate without violating the budget k in any dimension d>=3. Thus, we focus on obtaining biapproximation algorithms. For d=2, the biapproximation guarantee is (1+epsilon,3), i.e., for any epsilon>0, our scheme outputs a solution of size 3k and cost at most (1+epsilon) times the optimum. For fixed d>2, we present a (1+epsilon,O((1/epsilon)log k)) biapproximation algorithm.
BibTeX  Entry
@InProceedings{nagarajan_et_al:LIPIcs:2015:5315,
author = {Viswanath Nagarajan and Kanthi K. Sarpatwar and Baruch Schieber and Hadas Shachnai and Joel L. Wolf},
title = {{The Container Selection Problem}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)},
pages = {416434},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897897},
ISSN = {18688969},
year = {2015},
volume = {40},
editor = {Naveen Garg and Klaus Jansen and Anup Rao and Jos{\'e} D. P. Rolim},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2015/5315},
URN = {urn:nbn:de:0030drops53153},
doi = {10.4230/LIPIcs.APPROXRANDOM.2015.416},
annote = {Keywords: nonmetric kmedian, geometric hitting set, approximation algorithms, cloud computing, cross platform scheduling.}
}
13.08.2015
Keywords: 

nonmetric kmedian, geometric hitting set, approximation algorithms, cloud computing, cross platform scheduling. 
Seminar: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)

Issue date: 

2015 
Date of publication: 

13.08.2015 