Reducing the parallel complexity of certain linear programming problems (extended abstract)
Pravin M. Vaidya · Foundations of Computer Science · 1990
We study the parallel complexity of solving linear programming problems in the context of interior point methods. Let n and m respectively denote the number of variables and the number of constraints in the given problem. We give an algorithm that solves linear programming problems in O( (~nn)'/~ (l~gm)~ L) time using O(M(n)m/n + n3) processors. (M(n) is the number of operations for multiplying two nXn matrices.) This gives an improvement in the parallel running time for n =o(m). A typical case where n = o(m) is the dual of the uncapacitated transporta- tion problem. Our algorithm solves the uncapacitated transportation problem in O( ( VE)'/4 (10gV)~ (log V7)) time using O( V3) processors where V (E) is the number of nodes (edges) and 7 is the largest magnitude of an edge cost or a demand at a node. As a byproduct we also obtain a better parallel algorithm for the assign- ment problem for graphs of moderate density.