Minimizing $\sum_{i=1}^n \max(|x_i - x|, |y_i - y|)$ - Sum of Max of Absolute Values

Question

Suppose there are $n$ points $(x_i, y_i)$ for $i = 1,\ldots,n$. Please find another point $(x, y)$ to minimize function: $$\sum_{i=1}^n \max(|x_i - x|, |y_i - y|)$$

Answer 1

You can use the equivalent linear program

$$\min_{t,x,y} \sum_{i=1}^n t_i\\ \text{subject to } -t_i\leq x-x_i\leq t_i\\ -t_i\leq y-y_i\leq t_i, \text{for }i=1,\dots,n.$$