Towards a Genuinely Polynomial Algorithm for Linear Programming

A linear programming algorithm is called genuinely polynomial if it requires no more than $p(m,n)$ arithmetic operations to solve problems of order m × n, where p is a polynomial. It is not known whether such an algorithm exists. We present a genuinely polynomial algorithm for the simpler problem of solving linear inequalities with at most two variables per inequality. The number of operations required is O(mn³ log m). The technique used was developed in a previous paper where a novel binary search idea was introduced.