A polynomial time algorithm for solving systems of linear inequalities with two variables per inequality
- 1 October 1979
- proceedings article
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
We present a constructive algorithm for solving systems of linear inequalities (LI) with at most two variables per inequality. The algorithm is polynomial in the size of the input. The LI problem is of importance in complexity theory since it is polynomial time (Turing) equivalent to linear programming. The subclass of LI treated in this paper is also of practical interest in mechanical verification systems, and we believe that the ideas presented can be extended to the general LI problem.Keywords
This publication has 3 references indexed in Scilit:
- Deciding Linear Inequalities by Computing Loop ResiduesJournal of the ACM, 1981
- Simplification by Cooperating Decision ProceduresACM Transactions on Programming Languages and Systems, 1979
- Two-Commodity FlowJournal of the ACM, 1978