Minimize the sum of distance under maximum norm Given a set of points (Xi, Yi). I need to find a point (doesn't have to be in the given set) that minimize the sum of distance to the other points. The tricky part is the distance is measured by max(|X-Xi|, |Y-Yi|).
I found it hard to reason about because of the max function. Algorithms that apply to manhattan distance don't seem to apply.
 A: You want to find a point $(a,b)$ such that it is the solution to the following optimization problem:
\begin{align}
\min &\sum_i \max(|a-x_i|,|b-y_i|)
\end{align}
Let's do some voodoo.
\begin{align}
\min &\sum_i d_i\\
d_i&\geq|a-x_i| \qquad \forall i\\
d_i&\geq|b-y_i| \qquad \forall i\\
\end{align}
Let's do some more voodoo.
\begin{align}
\min &\sum_i d_i\\
d_i&\geq (a-x_i) \qquad \forall i\\
d_i&\geq -(a-x_i) \qquad \forall i\\
d_i&\geq (b-y_i) \qquad \forall i\\
d_i&\geq -(b-y_i) \qquad \forall i\\
\end{align}
Guess what? The problem is Linear and very simple to solve.
A: We want to find a point $y \in \mathbb{R}^m$ that minimizes the maximum distance to a set of $n$ points, given by sample matrix, $X\in \mathbb{R}^{n \times m}$, 
$$\min_y \max\{|x_i-y|,i=1,\dots,n\}.$$
As the maximum is applied component-wise, we can find element $y_j$ that minimizes the maximum norm by solving the folling linear optimization problem:
\begin{align}
\min_{y_j,d_{ij}}\ & \sum_i d_{ij} \\
s.t.\ & d_{ij} \geq x_{ij} -y_j \\
& d_{ij} \geq y_j -x_{ij} \\
& d_{ij} \geq 0,\ y_j\in \mathbb{R}.
\end{align}
This was the answer in the previous post. Now, we do not need an LP solver to find the optimum, because only those two constraints can be binding, where the difference between $x_{ij}$ and $y$ is largest, which are $\underline{x}_j = \max\{x_{ij}, i=1,\dots,n\}$ and $\overline{x}_j = \min\{x_{ij}, i=1,\dots,n\}$. It is easy to see that the value that jointly minimizes the distance to $\underline{x}_j$ and $\overline{x}_j$ is
$$ y_j^* = \frac{\underline{x}_j+\overline{x}_j}{2}.$$
Hence you only need to obtain the colmumn-wise minimum and maximum and compute its arithmetic mean.
