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,\dots ,P_n\in {‐{R}}^d$ with non‐negative weights $w_i$ and a point $P_0$ the task is to find new non‐negative weights ${\tilde{w}}_i$ such that $P_0$ is a 1‐median with respect to the new weights and ${\parallel w‐\tilde{w}\parallel }_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.