% Use the option doublespacing or reviewcopy to obtain double line spacing
% \documentclass[doublespacing]{elsart}

% if you use PostScript figures in your article
% use the graphics package for simple commands
% \usepackage{graphics}
% or use the graphicx package for more complicated commands
% \usepackage{graphicx}
% or use the epsfig package if you prefer to use the old commands
% \usepackage{epsfig}

% The amssymb package provides various useful mathematical symbols

\documentclass{ctwart}
\newcommand{\Real}{{\mathbb R}}

\usepackage{amsfonts, amsmath,  amssymb, graphics}
\DeclareMathOperator*{\ex}{ex}
\DeclareMathOperator*{\ib}{ib}
\begin{document}

\begin{frontmatter}


\title{The Inverse 1-Median Problem in $\mathbb R^d$ with the Chebyshev-Norm \thanksref{label1}}
\thanks[label1]{This research has been supported by the Austrian Science Fund
   (FWF) Project \mbox{P18918-N18}}
\author{Johannes Hatzl}

\address{Institute of Optimization and Discrete Mathematics\\ Graz University
   of Technology\\Steyrergasse 30, 8010 Graz, Austria}
\ead{hatzl@opt.math.tugraz.at}
\begin{keyword}
1-median problem \sep inverse location problem \sep fractional $b$-matching
problem \sep parametric flow problem
\end{keyword}
\end{frontmatter}
\section{Introduction}
This paper focuses on the weighted 1-median problem  in $\Real^d$ where the distance of two
points is measured by the  Chebyshev-norm. So far this problem is only
well understood for $d=2$. In this case, a linear time
algorithm is given in Hamacher \cite{Hamacher1995}.
In this note, we give the first combinatorial algorithm for $d \geq 3$.
Furthermore, we discuss an optimality criterion for the $d$-dimensional
case which is based on linear programming. Using this optimality criterion 
we are able to solve the inverse location problem.
In the inverse problem the facility  is already given
and the task is to modify  the weights of the points at minimum cost such that 
the given facility is a 1-median with respect to the new weights.
\section{The 1-median problem}\label{probform}
The 1-median problem discussed in this note is defined as follows: 
Given $n$ points $P_1, \ldots, P_n$ with 
$P_i = (x_1^i, \ldots, x_d^i) \in \Real^d$ for $i=1,\ldots,n$ and associated
non-negative  weights $w_i$ the task is to find a point  $P^\ast = (x_1^\ast, \ldots,
x_d^\ast) \in \Real^d$ such that
$$
\sum_{i=1}^n w_i \, \|P_i-P\|_{\infty} \geq \sum_{i=1}^n w_i \, \|P_i-P^\ast\|_{\infty}
$$
for all $P \in \Real^d$. Note that using some straightforward techniques the problem  
$
 \min_{P=(y_1,\ldots,y_d) \in \Real^d}\,\,  \sum_{i=1}^n  w_i \,\,
 \|P_i-P\|_{\infty}
$
can be written as a linear programming problem in the following form:
 \begin{alignat}{6}
 &\min          &\quad& \sum_{i=1}^n  w_i \, z_i &&   \label{lp1}  \\
 &\text{ s.t. } && z_i + y_j \geq   x_j^i   &&\quad i=1,\ldots,n, \,\,\, j=1, \ldots, d
 \label{lp2}\\
 &              && z_i - y_j \geq - x_j^i   &&\quad i=1,\ldots,n, \,\,\, j=1, \ldots, d
 \label{lp3}\\
 &              && y_j \in \Real,  \,\,\, z_i \in \Real  &&\quad j=1,\ldots,d, \,\,\, i=1,\ldots,n. \label{lp4}
 \end{alignat}
Due to the fact that the variables $y_j$ do not appear in the objective
function, we use the well known Fourier-Motzkin
elimination to get rid of these variables in the constraints. We obtain the
following equivalent problem
\begin{alignat*}{6}
&\min          &\quad& \sum_{i=1}^n  w_i \, z_i &&    \\
&\text{ s.t. } && z_i + z_k \geq  d^{i k}    &&\quad i = 1, \ldots, n   
\,\,\, k=1,\ldots,n\\
&              && z_i \geq 0                && \quad i=1, \ldots ,n
\end{alignat*}
where $d^{ik} := \max_j | x_j^i - x_j^k|$. It is easy to see that
the corresponding dual problem is   the linear relaxation of the
maximum-weight-$b$-matching  problem on a complete graph. It is 
shown in Antsee \cite{Antsee87} that  this graphtheoretical 
problem can be solved by a min-cost-flow problem in a bipartite graph.
\section{The Inverse Problem}
An instance of the inverse problem is given by a set of $n$ points $P_1,
\ldots, P_n \in \Real^d$ with corresponding non-negative weights $w_i\geq
0$ and a point $P_0$ (which may coincide with a given point). The task is to
find new weights $\tilde w_i \geq 0$ such that $P_0$ is a
1-median with respect to $\tilde w_i$ and  $\|w - \tilde w\|_1$
is minimized. The problem can be formulated in a compact form as follows:
\begin{alignat*}{6}%\label{test}
&\min          &\quad&   \sum_{i=1}^n  |w_i - \tilde w_i|       &&     \\
&\text{ s.t. } &&  \sum_{i=1}^n \tilde w_i \, \|P_i-P\|_{\infty} \geq
\sum_{i=1}^n ¸\tilde w_i \, \|P_i-P_0\|_{\infty}     &&\quad \forall P \in \Real^d\\
&              &&  \tilde w_i \geq 0                      &&\quad  i=1,\ldots,n.
\end{alignat*}
Before we give a combinatorial algorithm we state the following lemma.
\begin{lem}\label{lem:red}
There exists an optimal solution $w^\ast$ of the inverse location problem such that $w_i
\geq w^\ast_i$ holds for all $i=1, \ldots,n$.
\end{lem}
Let us consider the dual linear programming problem of
\eqref{lp1}---\eqref{lp4}. We introduce non-negative dual 
variables $u_{i,j}$ for the constraints \eqref{lp2} and  non-negative dual
variables $v_{i,j}$ for the constraints \eqref{lp3} and obtain
\begin{alignat*}{6}
&\max          &\quad& \sum_{i=1}^n \sum_{j=1}^d  x_j^i \left(u_{i,j} - v_{i,j}\right) &&   \\
&\text{ s.t. } &&\sum_{j=1}^d \left( u_{i,j} + v_{i,j}\right) = w_i   &&\quad
i=1,\ldots,n \\
%\label{duallp2}\\
&              &&\sum_{i=1}^n u_{i,j}  =  \sum_{i=1}^n v_{i,j}   &&\quad
j=1,\ldots,d \\
%\label{duallp3}\\
&              && u_{i,j} \geq 0,  \,\,\, v_{i,j} \geq 0
&&\quad  i=1,\ldots,n, \,\,\, j=1, \ldots,d.
\end{alignat*}
In order to interpret the dual problem let us construct the following flow problem:
Consider the bipartite graph  $G = (V_1 \cup V_2, E)$
where  the set $V_1$ consists of $n$ vertices, one for each point $P_i$ of the 1-median problem.
The set $V_2$ has exactly $2d$ vertices representing the closed cones
$$
Q_j^\geq :=\{x \in \Real^d:x_j \geq 0  \text{ and }
|x_j| \geq |x_k| \,  \forall k=1, \ldots,d\}
$$
and
$$
Q_j^\leq :=\{x \in \Real^d:x_j \leq 0  \text{ and }
|x_j| \geq |x_k| \,  \forall k=1, \ldots, d\}
$$
for $j=1,\ldots, d$. We have an edge $(P_i,Q_j^\sim)$ if  $P_i$ is in the cone $Q_j^\sim$ 
($\sim \in \{\leq,\geq\}$). Moreover, we set the capacity $u(e)$ of the edges of the bipartite graph to infinity. 
Furthermore, we add a source $s$ and the edges $(s,P_i)$ for all $i=1, \ldots, n$ with
$u(s,P_i) = w_i$. Finally, we introduce a sink $t$ and an edge from each vertex
in $V_2$ to $t$ with infinite capacity. We denote this network by  $I(P_1,\ldots,P_n,w)$.
Furthermore, a flow in  $I(P_1,\ldots,P_n,w)$ is called  perfect
if  the flow on the edges $(Q_j^\geq, t)$ and $(Q_j^\leq,t)$ is equal for all
$j$. The value of a flow is denoted by $v(f)$. Now we can state the following theorem.
\begin{thm}\label{thm}
Suppose we are given $n$ points $P_1, \ldots, P_n \in \Real^d$ with
non-negative weights $w_i \geq 0$. Then, the origin $P^\ast=(0, \ldots,0)$ is an
optimal solution of the 1-median problem if and only if there exists a perfect
flow $f$ in $I(P_1,\ldots,P_n,w)$ such that $v(f) = \sum_{i=1}^n w_i$.
\end{thm}
\begin{exmp}
Suppose we are given the following points: $P_1=(-1,3)$, $P_2=(2,2)$,
\mbox{$P_3=(4,-1)$}, $P_4=(2,-2)$, $P_5=(0,-2)$ and $P_6=(-4,1)$ with the
weights $w_1=3$, $w_2=1$, $w_3=1$, $w_4=2$, $w_5=2$ and $w_6=3$. Then, the
corresponding instance  $I(P_1,\ldots,P_n,w)$ of the balancing flow problem  admits
a perfect flow $f$ with $v(f) = \sum_{i=1}^n w_i$ (see
Figure \ref{fig}). Thus, we can conclude that the origin is a 1-median.
\begin{figure}[htpb]
\begin{center}
\resizebox{5.4cm}{!}{\includegraphics{graph1.eps}}
\resizebox{6.3cm}{!}{\includegraphics{graph.eps}}
\caption{On the left hand side we are given an instance of the 1-median
  problem where the cone $Q_1^\geq$ is highlighted. The right hand side 
  shows the graph of the balancing flow problem (without the supersink $t$). On the edges a perfect flow is given.}
\label{fig}
\end{center}
\end{figure}
\end{exmp}
It is easy to see that the inverse problem can be solved by the following algorithm:
\begin{algorithm}[h!]
\begin{alg}
Step 1: Construct the instance $I(P_1,\ldots,P_n,w)$\\
Step 2: Find a perfect flow $f$ in $I(P_1,\ldots,P_n,w)$ that maximizes $v(f)$\\
Step 3: The new weights are given by $w^\ast_i = f(s,P_i)$\\
\end{alg}
\end{algorithm}\\
The main step is obviously the computation of a maximum
perfect flow in Step 2. The maximum perfect flow problem can be reformulated as a parametric flow
problem, where capacities on the edges $(Q_j^\geq,t)$ and
$(Q_j^\leq,t)$ are given by a parameter $\lambda_j$. 
If we maximize
$$%\begin{equation}\label{parflow}
2 \sum_{j=1}^d \lambda_j
$$%\end{equation}
such that there exists a flow $f$ that saturates all the edges entering the
supersink $t$, the flow $f$ is a maximum perfect flow. This maximization problem
is closely related to parametric flow problems discussed in
McCormick \cite{McCormick1996} and can indeed be solved in polynomial time.


\bibliographystyle{00}  
\begin{thebibliography}{00}

\bibitem{Antsee87} R.\ Antsee, A polynomial algorithm for {$b$}-matchings: an alternative
              approach. \emph{Inform. Process. Lett.} (1987), 153--157.
\bibitem{Hamacher1995} H.\ Hamacher, Mathematische L{\"o}sungsverfahren 
f{\"u}r planare Standortprobleme. Braunschweig/Wiesbaden: Vieweg (1995).
\bibitem{McCormick1996} 
T.\ McCormick, Fast algorithms for parametric scheduling come from extensions
to parametric maximum flow.  In \emph{STOC '96: Proceedings of the
twenty-eighth annual ACM symposium on Theory of computing} (1996), 319--328.


\end{thebibliography}



% \bibitem{label}
% Text of bibliographic item

% notes:
% \bibitem{label} \note

% subbibitems:
% \begin{subbibitems}{label}
% \bibitem{label1}
% \bibitem{label2}
% If there is a note, it should come last:
% \bibitem{label3} \note
% \end{subbibitems}

%\bibitem{}


\end{document}

