minimizing $\sum_{i=1}^n \max(|x_i - x|, |y_i - y|)$

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|)$$

-
Looks like a small linear program. It's a guess, but I think the median of $x_i$ and $y_i$ will minimize (but solution is probably not unique in general). –  hardmath Jul 17 '13 at 15:33

1 Answer

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.$$

-
+1, clever approach :) –  gt6989b Jul 17 '13 at 16:08
very clever approach :), but it is possible to find out the answer in O(n) time? I mean it is possible to get the answer in seconds with a compute even n = 100000? PS, I don't know how to use equivalent linear program till now :-) –  storm Jul 18 '13 at 7:33
Given that it is a particular linear program you might be able to solve it faster than a generic linear programming algorithm does, but I'm not sure if you can achieve $O(n)$ complexity. I don't know any fast algorithm off the top of my head, though. –  S.B. Jul 18 '13 at 13:36