Serving Online Demands with Movable Centers.
Abdolhamid Ghodselahi, Fabian Kühn · arXiv (Cornell University) · 2014
We study an online problem in which a set of mobile resources or centers have to be moved in order to optimally serve a set of demands. There is a set of $n$ nodes and a set of $k$ resources that are placed at some of the nodes. Each node can potentially host several resources and the resources can be moved between the nodes. At the nodes, demands arrive in an online fashion, and the cost for serving the demands is a function of the number of demands and resources at the different nodes. An online algorithm has to move resources in order to keep the service cost low, however as moving resources is expensive, the objective of an online algorithm is to minimize the total number of movements. Specifically, we give a deterministic online algorithm, which for parameters $\alpha\geq 1$ and $\beta\geq 0$ guarantees that at all times, the service cost is within a multiplicative factor $\alpha$ and an additive term $\beta$ of the optimal service cost and where also the movement cost is within a small multiplicative factor and an additive term of the optimal overall cost. Roughly, for $\alpha=1$ and $\beta=\Omega(k)$, we show that the movement cost by time $t$ is upper bounded by the optimal service cost at time $t$ plus an additive term of order $O(k\log k)$. For $\alpha>1$ and arbitrary $\beta$, we show that the movement cost by time $t$ is only linear in $k\log k$ and logarithmic in the optimal service cost at time $t$. We also show that both bounds are almost asymptotically tight.