|Abstract of Paper|
Faster Algorithms for k-Median Problems in Trees
by Robert R. Benkoczi, Binay K. Bhattacharya, Marek Chrobak, Lawrence L. Larmore, and Wojciech Rytter
In the k-median problem we are given a connected graph with non-negative weights associated with the nodes and lengths associated with the edges. The task is to compute locations of $k$ facilities in order to minimize the sum of the weighted distances between each node and its closest facility. The number $k$ is a constant. In this paper we give the first subquadratic time algorithms (in fact linear time within a polylogarithmic factor) for directed trees, for balanced undirected trees, and for general undirected trees with $k=3$.