Taxicab distances: L1 norm minimization

From this post:

Suppose we are given $n$ points $A_1, \dots, A_n \in \mathbb{R}^2$. The task is to find a point $x = (x_1,x_2) \in \mathbb{R}^2$ such that the sum of distances to the points $A_1, \dots, A_n$ in the $\ell_1$-norm is minimized. Formulate this problem as a linear program.

There are at least two (primal) formulations. A variable splitting technique can look like:

$$\boxed{\begin{align}   \min & \sum_{i,j} y^+_{i,j} + y^-_{i,j}\\   &y^+_{i,j} - y^-_{i,j} = x_j-A_{i,j}\\   &y^+_{i,j}\ge 0, y^-_{i,j}\ge 0 \end{align}}$$

A different formulation is

$$\boxed{\begin{align}   \min & \sum_{i,j} y_{i,j}\\   &-y_{i,j} \le x_j-A_{i,j} \le y_{i,j}\\   &y_{i,j}\ge 0 \end{align}}$$

I don’t think this formulation has a name. We can drop $y_{i,j}\ge 0$ if we want, as this is implied by $-y_{i,j}\le y_{i,j}$.

If you let mathematicians loose on this, you may end up with formulation 2 stated as:

$$\boxed{\begin{array}{ll} \text{minimize} & 1_{2n}^{\top} \mathrm y\\ \text{subject to} & -\mathrm y \leq (1_n \otimes \mathrm I_2) \, \mathrm x - \mbox{vec} (\mathrm A) \leq \mathrm y\\ & \mathrm y \geq 0_{2n}\end{array}}$$

I don’t really like this type of notation: at least for me it is much less intuitive.

The first formulation has fewer equations but more variables. The second formulation has more constraints as we need to split $-y_{i,j} \le x_j-A_{i,j} \le y_{i,j}$ into $x_j-A_{i,j} \ge –y_{i,j}$ and $x_j-A_{i,j} \le y_{i,j}$. I don’t think there is much reason to choose one formulation above the other. Depending largely on my mood I use either version 1 or 2.