Fast finite methods for a system of linear inequalities

Abstract1Several algorithms are known that solve a system of m linear inequalities in n variables using a polynomial number of steps in m and n for all inputs. The simplex method runs in polynomial time in the average case (proven) and requires only linear in m number of steps in practice. We consider a family of finite algorithms; some of them involve O(m/n) log3 n iteration steps in the average case under a certain additional assumption about the behavior of the computed approximations to a solution and only O(m(m + n)) arithmetical operations are required per step. The theoretical study is confirmed by some numerical experiments. Also two methods are presented that enable us to turn any converging algorithm for a system of linear inequalities with real inputs into an algorithm that converges in a finite number of steps