Efficient Algorithms for the Capacitated 1-Median Problem

The 1-median problem is to locate a service facility so as to minimize the sum of the distances from a given set of demand destinations. In this paper, we develop a data storage scheme which is useful for dealing with sums of rectilinear (L₁) distances in space and travel distances along the edges of a tree network. We then use this scheme to provide efficient algorithms to various capacitated 1-median problems.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.