The pos/neg-weighted 1-median problem on tree graphs with subtree-shaped customers

In this paper we consider the pos/neg-weighted median problem on a tree graph where the customers are modeled as continua subtrees. We address the discrete and continuous models, i.e., the subtrees’ boundary points are all vertices, or possibly inner points of an edge, respectively. We consider two different objective functions. If we minimize the overall sum of the minimum weighted distances of the subtrees from the facilities, there exists an optimal solution satisfying a generalized vertex optimality property, e.g., there is an optimal solution such that all facilities are located at vertices or the boundary points of the subtrees. Based on this property we devise a polynomial time algorithm for the pos/neg-weighted 1-median problem on a tree with subtree-shaped customers.