PLACING RESOURCES ON A GROWING LINE

We consider the problem of placing k identical resources in a graph wh ere each vertex is associated with a nonnegative weight representing t he frequency of requests issued by that vertex for the resource. We de fine the cost of a placement as the sum over all vertices of their dis tances to the closest resource weighted by their weights. The optimal placement is the placement with the least cost among all placements. W e give an algorithm for placing optimally k resources on a ''growing'' line. The algorithm starts with an empty line. At each step a new ver tex is appended to the line and the algorithm has to recompute the opt imal placement of the k resources. Our algorithm processes each new ve rtex in O(k) amortized time. As a corollary, we obtain an algorithm th at computes the optimal placement of k resources in an n-vertex line i n time O(kn), which is optimal for constant k. (C) 1998 Academic Press .