A Polynomial Time Algorithm for Solving Systems of Linear Inequalities with Two Variables Per Inequality

Authors:
  • BABengt Aspvall
    Bengt Aspvall
  • YSYossi Shiloach
    Yossi Shiloach

Abstract
We present a constructive algorithm for solving systems of linear inequalities (LI) with at most two variables per inequality. The time complexity of the algorithm is $O(mn^3 I)$ on a random access machine, where m is the number of inequalities, n the number of variables, and I the size of the binary encoding of the input. The LI problem is of importance in complexity theory because it is polynomial time (Turing) equivalent to linear programming. The subclass of LI treated in this paper is of practical interest in mechanical verification systems.

This publication has 5 references indexed in Scilit: