Inverse 1-median Problem on Trees under Weighted l∞ Norm

The inverse 1-median problem is concerned with modifying the weights of the customers at minimum cost such that a prespecified supplier becomes the 1-median of modified location problem. We first present the model of inverse 1-median problem on trees. Then we propose two algorithms to solve the problem under weighted l(infinity) norm with bound constraints on modifications. Based on the approach of the unbounded case, we devise a greedy-type algorithm which runs in O(n(2)) time, where n is the number of vertices. Based on the property of the optimal solution, we propose an O(n log n) time algorithm using the binary search.