A Linear-Time Algorithm for Maxisum Facility Location on Tree Networks

This paper treats a topic in “obnoxious facility location,” namely the problem of locating a single facility in an n-vertex tree network so as to maximize the sum of its weighted distances from the vertices. It is shown that use of a suitable data structure permits a solution algorithm with computational effort O(n), an improvement over the O(n²) required by a previously indicated procedure.