|
Abstract : |
Abstract. The parallel time complexity of the linear programming problem with at most two variables per inequality is discussed. Let n and m denote the number of variables and the number of inequalities, respectively, in a linear programming problem. We assume all inequalities are weak. We describe an O((log m +log 2 n) log 2 n)-time parallel algorithm for deciding feasibility, under the concurrent-read-exclusive-write PRAM model. It requires mn O(log n) processors in the worst case, though we do not know whether this bound is tight. When the problem is feasible a solution can be computed within the same complexity. Moreover, linear programming problems with at most two nonzero coe cients in the objective function can be solved in poly-log time on a similar number of processors. Consequently, all these problems can be solved sequentially with only O((log m +log 2 n) 2 log 2 n) space. (These bounds assume that numbers take O(1) space, and arithmetic on them takes O(1) time ? the problem can still be solved in poly-log space as a function of the input size even if we instead use a Turing machine model with rational input.) It is also shown that if the underlying graph has bounded tree-width and an underlying tree is given then the feasibility problem is in the class NC. 1., |
