# Minimized sum of the distances with street distance

This exercise comes from Bazaraa Linear Programming and Network Flows book :

Consider the problem of locating a new machine to an existing layout
consisting of four machines. These machines are located at the following coordinates in two-dimensional space: $(3,1) ,(0,-3) ,(-2,2)$ and $(1,4)$. Let the coordinates of the new machine be $(x_1,x_2)$ .

The sum of the distances from the new machine to the four machines is minimized. Use the street distance (also known as Manhattan distance or rectilinear distance); for example, the distance from $(x_1,x_2)$ to the first machine located at (3,1) is $|x_1 - 3| + |x_2 - 1|$·

the solution is definitely minimized $$|x_1 - 3| + |x_2 - 1| + |x_1 - 0| + |x_2 + 3| + |x_1 + 2| + |x_2 - 2| + |x_1 - 1| + |x_2 - 4|$$

But a solution guide I saw adds this :

$$|x_1 - 3| + |x_1 - 0| + |x_1 + 2| + |x_1 - 1| \geq 6$$ $$|x_2 - 1| + |x_2 + 3| + |x_2 - 2| + |x_2 - 4| \geq 10$$

I know those are sum of absolute values of specified points' location. But I can't figure out the whole reason of above solution. Has anyone figured out?

-

The values of $x_1$ and $x_2$ that make the distance (street distance) a minimum are $0 \le x_1 \le 1$ and $1 \le x_2 \le 2$. Here's what I did:

Let $d_x(x_1)$ be the distance in the $x$ axis and $d_y(x_2)$ be the distance in the $y$ axis, given by:

$d_x(x_1)=|x_1 - 3|+ |x_1 - 0| + |x_1 + 2|+ |x_1 - 1|$

$d_y(x_2)= |x_2 - 1| + |x_2 + 3| + |x_2 - 2| + |x_2 - 4|$

Minimizing each function will give the coordinates $(x_1,x_2)$ that makes the total distance a minimum. The problem is the absolute value, so I got rid of it expressing $d_x(x_1)$ and $d_y(x_2)$ as piecewise functions:

$$d_x(x_1)= \left\{ \begin{array}{1 1} -4x_1+2 & \quad x_1 \le -2 \\ -2x_1 +6 & \quad -2 < x_1 \le 0 \\ 6 & \quad 0 < x_1 \le 1 \\ 2x_1+4 & \quad 1 < x_1 \le3 \\ 4x_1-2 & \quad x_1 \ge 3 \end{array} \right.\$$

$$d_y(x_2)= \left\{ \begin{array}{1 1} -4x_2+4 & \quad x_1 \le -3 \\ -2x_2 +10 & \quad -3 < x_1 \le 1 \\ 8 & \quad 1 < x_2 \le 2 \\ 2x_2+4 & \quad 2 < x_2 \le 4 \\ 4x_2-4 & \quad x_2 \ge 4 \end{array} \right.\$$

Here it is clear that the minimums are $6$ and $8$ (not $10$ as you said $|x_2 - 1| + |x_2 + 3| + |x_2 - 2| + |x_2 - 4| \ngeq 10$ )

-