The K-Coverage problem
Zhang Yan
Department of Computer Science
HKUST

November 21, 2003
11-11:50 AM
Room 3501, HKUST


Abstract
--------
The k-coverage problem is to place $k$ similar resources 
in a graph.  The cost of a vertex is given by a step function 
of the distance to its closest resource.
The cost of a placement is the sum of theses costs over all vertices.
The optimal placement is the placement with least cost among all
placements.

Our specific problem is an online problem where the graph is a line.
We start with an empty line.
In each step, a new vertex is appended to one end of the line and the
algorithm has to recompute the optimal placement for the k resources.

Our approach is to  extend the techniques in [1].
The algorithm processes each new vertex in O(k)  amortized time
and in O(k \log n) worst case simultaneously.

[1]  V. Auletta, D. Parente and G. Persiano.
Placing Resources on a Growing Line.
Journal of Algorithms, v26, 1998, p87-100.