2-medians in trees with pos/neg weights

This paper deals with facility location problems with pos/neg weights in tr ees. We consider two different objective functions which model two differen t ways to handle obnoxious facilities. If we minimize the overall sum of th e minimum weighted (distances Of the vertices from the facilities, the opti mal solution has nice combinatorial properties, e.g., vertex optimality. Fo r the pos/neg 2-median problem on a network with n vertices, these properti es can be exploited to derive an O(n(2)) algorithm for trees, an O(n log n) algorithm for stars and a linear algorithm for paths. For the p-median pro blem with pos/neg weights on a path we give an O(pn(2)) algorithm. If we mi nimize the overall sum of the weighted minimum distances of the vertices fr om the facilities, we can show that there exists a finite set of O(n(3)) po ints in the tree which contains the locations of facilities in an optimal s olution. This leads to an O(n(3)) algorithm for finding the optimum 2-media ns in a tree. The complexity can be reduced to O(n(2)), if the medians are restricted to vertices or if the tree is a path. (C) 2000 Elsevier Science B.V. All rights reserved.