I have a linear program with $n$ variables, $m$ constraints and $O(nm)$ bit total length (the constraint matrix contains only zeros and ones). I am interested in finding a polynomial time algorithm for exact solving of the linear program, where the dependency on $m$ is as small as possible. More formally:

The time complexity of solving the linear program is known to be $O(n^a m^b)$ for some constants $a$ and $b$. What is the best known pair $a, b$ where the value of $b$ is the minimum possible?

  • $\begingroup$ Do you want integer results, or just "real" (floating pont) ones? $\endgroup$
    – vonbrand
    Feb 19, 2020 at 0:41
  • $\begingroup$ Real (they are actually fractions with bounded bit length). For integers, no polynomial-time algorithm is known (it is NP-hard). $\endgroup$
    – Laakeri
    Feb 19, 2020 at 5:35


Your Answer

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