CATS-Sep-19-2014
Title[edit]
Approximation Algorithms for Container Selection Problems.
Speaker[edit]
Kanthi Kiran Sarpatwar
Abstract[edit]
I will discuss an interesting variant of the non-metric $k$-median problem that arises in cross platform scheduling. An instance of the container selection problem consists of $N$ input points in $R^d$ and a bound $k$. The goal is to compute $k$ container points in $R^d$ such that (i) every input point is assigned to some container point that dominates it, and (ii) the total assignment cost is minimized. The assignment cost of an input point is the $L_1$ norm of its assigned container point, which corresponds to the resource allocated to the input point. I will discuss some of the results we have for this problem and its variants.
This is joint work with Viswanath Nagarajan, Baruch Schieber, Hadas Shachnai and Joel Wolf.
