If you have an LP
$c_1|x_1| + c_2|x_2| ... c_n|x_n|$
$Ax = b$
Can this be solved in polynomial time with respect to the amount of data used to represent the problem?
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.Sign up to join this community
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.