If you have an LP


$c_1|x_1| + c_2|x_2| ... c_n|x_n|$

Subject to:

$Ax = b$

Can this be solved in polynomial time with respect to the amount of data used to represent the problem?

  • $\begingroup$ On average? Yes. In every case, I don't think so. See if this helps. Of course, simplex is not the only option, so ... $\endgroup$ – AnonSubmitter85 Jun 30 '13 at 3:57
  • $\begingroup$ If Ax = b specifies a unit hypercube located in the all positive quadrant, with a corner at 0,0,0,0...0 and the absolute value was basically measuring the absolute value of $x_i - 1/2$ for all the $x_i$ in x $\endgroup$ – frogeyedpeas Jun 30 '13 at 6:08

For minimizing you can translate this to a standard linear program.

minimize $\sum_i c_i y_i$ s.t. $Ax=b$, $y_i \ge x_i$, and $y_i \ge -x_i$. $y_i = |x_i|$ in any optimal solution. This is solvable in polynomial time, but not by the simplex method, although that is likely the fastest method.

For maximizing absolute value you have a NP hard problem. Consider the number partitioning problem. If the values to be partitioned are $w_i$. The optimization problem maximize $\sum_i |x_i|$ subject to $\sum_i w_i x_i = 0$, $x_i \le 1$, and $x_i \ge -1$ will have an optimal value of $|I|$ if and only there is a partitioning of the $w_i$ into two equal subsets.

  • 1
    $\begingroup$ +1. I believe your answer is correct except that in the first part (minimize) the objective function should be $\min$ $\sum_i c_iy_i$ not $\sum_i c_i x_i$ $\endgroup$ – Inquest Jun 30 '13 at 22:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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