A Polynomial Time Algorithm for Solving Systems of Linear Inequalities with Two Variables Per Inequality
Authors:
- Bengt AspvallBABengt Aspvall
- Yossi ShiloachYSYossi Shiloach
- 1 November 1980
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 9 (4) , 827-845
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.
Keywords
This publication has 5 references indexed in Scilit:
- Deciding Linear Inequalities by Computing Loop ResiduesJournal of the ACM, 1981
- Complexity, convexity and combinations of theoriesTheoretical Computer Science, 1980
- The complexity of linear programmingTheoretical Computer Science, 1980
- Simplification by Cooperating Decision ProceduresACM Transactions on Programming Languages and Systems, 1979
- Two-Commodity FlowJournal of the ACM, 1978