Assume we are given a LP maximization problem defined by a linear functional $c^Tx$ and a non-empty feasible region $\{x:Ax\leq b\}$ that is known to be bounded by a hypercube of side $R>0$, say $[0,R]\times \dots \times [0,R]$. Asume that problem data is real: $A\in\mathbb{R}^{m\times n}$, $b\in\mathbb{R}^{m\times1}$, $c\in\mathbb{R}^{n\times 1}$. Let $z$ be its optimal value.

What is, currently, "the best" approach to approximate by less than an absolute error of $\delta$ the optimal value $z$ of the problem? A strongly polynomial complexity bound in terms of the entries of the matrices, $m$, $n$ and $\delta^{-1}$ would be great. I'm interested in both theoretical bounds and (provable)bounds arising from algorithms for which efficient implementations are known.

I'm not sure if this reduces the complexity of the problem or not, but I'm not interested in obtaining a feasible solution $x$ such that $|c^Tx - z|<\delta$, I need only the real number $c^Tx$ approximating $z$.


Your Answer


Browse other questions tagged or ask your own question.