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

Abstract:

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$.