2-Medians in trees with pos/neg weights

AbstractThis paper deals with facility location problems with pos/neg weights in trees. We consider two different objective functions which model two different ways to handle obnoxious facilities. If we minimize the overall sum of the minimum weighted distances of the vertices from the facilities, the optimal solution has nice combinatorial properties, e.g., vertex optimality. For the pos/neg 2-median problem on a network with n vertices, these properties can be exploited to derive an O(n2) algorithm for trees, an O(nlogn) algorithm for stars and a linear algorithm for paths. For the p-median problem with pos/neg weights on a path we give an O(pn2) algorithm. If we minimize the overall sum of the weighted minimum distances of the vertices from the facilities, we can show that there exists a finite set of O(n3) points in the tree which contains the locations of facilities in an optimal solution. This leads to an O(n3) algorithm for finding the optimum 2-medians in a tree. The complexity can be reduced to O(n2), if the medians are restricted to vertices or if the tree is a path