Improved Algorithms For Linear Inequalities with Two Variables Per Inequality

Publisher Website
Google Scholar
Abstract
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 ($) over tilde O (mn(2)) time (we denote ($) over tilde O(f) = O(f polylog n polylog m)) deterministically, and in ($) over tilde O(n(3) + mn) expected time using randomization. parallel implementations of these algorithms run in ($) over tilde O(n) time, where the deterministic algorithm uses ($) over tilde O)(mn) processors and the randomized algorithm uses ($) over tilde On(2) + m) processors. The bounds significantly improve over previous algorithms. The randomized algorithm is based on novel insights into the structure of the problem.