Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I posted a question in http://math.stackexchange.com/ and got a solution. But the solution is a bit hard for me to understand. The actual question is here : minimizing $\sum_{i=1}^n \max(|x_i - x|, |y_i - y|)$

and solution was in the form of a linear program and is right there below the question:

what is $t_i$ in the solution? how can I obtain it?


1 Answer 1

For convenience I'll quote the author

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

$t_i$ is just a dummy variable that, by construction of the constraints, will assume the larger value of $|x - x_i|$ and $|y -y_i|$. What the author is doing is converting the problem into a general linear programming form, and suggesting the application of a common optimization algorithm (such as the simplex method) to find the solution. I do not have a sufficient background in linear programming to go into more detail than this. Perhaps someone who does can pick up where I leave off.


This site is currently not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .