Consider the following optimisation problem that its size is parameterised by $n$ (width) and $m$ (depth):

Find $w_1, w_2, \ldots, w_n$ that minmises: $$ \min \Big[w_1x_1^0 + w_2x_2^0 + \ldots + w_nx_n^0 \Big] $$

Subject to:

$$ b^1_{\min} \le w_1x_1^1 + w_2x_2^1 + \ldots + w_nx_n^1 \le b^1_{\max} $$ $$ b^2_{\min} \le w_1x_1^2 + w_2x_2^2 + \ldots + w_nx_n^2 \le b^2_{\max} $$ $$ \vdots $$ $$ b^m_{\min} \le w_1x_1^m + w_2x_2^m + \ldots + w_nx_n^m \le b^m_{\max} $$


  • $w_1, w_2, \ldots, w_n$ are variables that we must tune (by assigning real numbers to them) in order to solve the optimisation problem above.

  • for any $1 \le i \le n$ and $1 \le j \le m$, $x_i^j$ is a constant real number, and $b^j_{\min}, b^j_{\max}$ are bounds.

    Note that superscript $^j$ is not an exponent, but a second index. I thought it would be more readable to write $x_i^j$ than $x_{i,j}$.

Question: What's the best asymptotic worst run-time and space that we can get for a solver of this problem?

E.g. can it get as low as $O(nm)$? if not, what's the lowest we can achieve?


1 Answer 1


This is an instance of linear programming, so you can solve it with any LP solver.

Any instance of linear programming can be represented in this form. For instance, minimize $c^\top w$ subject to $Aw \le b$ can be represented by setting $b^i_\max = b_i$, $x^i_j = A_{i,j}$, $b^i_\min=-\infty$, $x^0_j=c_j$. Therefore, you can't expect any special-case algorithm that is more efficient than general-purpose linear programming.

The worst-case complexity of linear programming is polynomial but a bit messy, but in practice it is often very efficient on real-world instances.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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