Bots, Bureaucrats, editor
84
edits
Changes
From Theory
Created page with "== Title == Approximation Algorithms for Container Selection Problems. == Speaker == Kanthi Kiran Sarpatwar == Abstract == I will discuss an interesting variant of the non-m..."
== Title ==
Approximation Algorithms for Container Selection Problems.
== Speaker ==
Kanthi Kiran Sarpatwar
== Abstract ==
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.
Approximation Algorithms for Container Selection Problems.
== Speaker ==
Kanthi Kiran Sarpatwar
== Abstract ==
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.
