Sign up ×
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 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?

share|cite|improve this question

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.