using linear programming to find median

Question

I'm trying to figure out how to transform a median solving problem for a list of number x to linear programming and with standard form of $$\text{min }c^Tx \text{ s.t: } Ax\le b \text{ and }x \geq 0$$

I know that we need to use l1 norm to find median and median = $$argmin \sum|m-xi|$$

but I'm not sure how to transform this absolute value to an optimization question in standard form.

Answer 1

Let $z_i = |m-x_i|$, then the problem becomes

$$\min_{m,z_1, \ldots, z_n} \sum_i z_i$$

subject to $z_i \ge m-x_i, z_i \ge x_i -m, \forall i \in \{1, n\}$.

I will leave the task of converting it to standard form to you.