## 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 ⊂ 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.

Original language | English (US) |
---|---|

Title of host publication | Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 18th International Workshop, APPROX 2015, and 19th International Workshop, RANDOM 2015 |

Editors | Naveen Garg, Klaus Jansen, Anup Rao, Jose D. P. Rolim |

Publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |

Pages | 416-434 |

Number of pages | 19 |

ISBN (Electronic) | 9783939897897 |

DOIs | |

State | Published - Aug 1 2015 |

Externally published | Yes |

Event | 18th 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 2015 → Aug 26 2015 |

### Publication series

Name | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|

Volume | 40 |

ISSN (Print) | 1868-8969 |

### Conference

Conference | 18th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2015, and 19th International Workshop on Randomization and Computation, RANDOM 2015 |
---|---|

Country/Territory | United States |

City | Princeton |

Period | 8/24/15 → 8/26/15 |

## All Science Journal Classification (ASJC) codes

- Software

## Keywords

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