Online Maintenance of k-Medians on a Line
Zhang Yan
Friday, March 5, 2004.
11-12, room 3464




Abstract
--------

The k-median problem is to choose k nodes from the 
given graph to place resources so as to minimize 
the sum of the distance of each node from its closest 
resource. This is NP-hard in general graphs but, in line 
graphs, the static version of the problem can be solved 
in O(kn) time for n nodes. We consider the online
version in which points are added one by one to the 
right of the line   and show that the k-medians can 
be updated in O(k) amortized time and O(k log(n)) 
worst case time per step.

This is joint work with R. Fleischer and M. Golin