2-balanced flows and the inverse 1-median problem in the Chebyshev space

In this paper, we consider the 1-median problem in R d with the Chebyshev-norm. We give an optimality criterion for this problem which enables us to solve the following inverse location problem by a combinatorial algorithm in polynomial time: Given n points P 1 , … , P n ∈ R d with non-negative weights w i and a point P 0 the task is to find new non-negative weights w i such that P 0 is a 1-median with respect to the new weights and ‖ w − w ‖ 1 is minimized. In fact, this problem reduces to a 2-balanced flow problem for which an optimal solution can be obtained by solving a fractional b -matching problem.