# Time complexity of linear programming with small number of variables

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?

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