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 '20 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 '20 at 5:35

Your Answer

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

Browse other questions tagged or ask your own question.