Improved Algorithms For Linear Inequalities with Two Variables Per Inequality
Edith Cohen, Nimrod Megiddo · SIAM Journal on Computing · 1994
The authors show that a system of m linear inequalities with n variables, where each inequality involves at most two variables, can be solved in $\tilde O(mn^2 )$ time (we denote $\tilde O(f) = O(f{\operatorname{polylog}} n{\operatorname{polylog}} m))$ deterministically, and in $\tilde O(n^3 + mn)$ expected time using randomization. Parallel implementations of these algorithms run in $\tilde O(n)$ time, where the deterministic algorithm uses $\tilde O(mn)$ processors and the randomized algorithm uses $\tilde O(n^2 + m)$ processors. The bounds significantly improve over previous algorithms. The randomized algorithm is based on novel insights into the structure of the problem.