Parallel linear programming in fixed dimension almost surely in constant time

Abstract

It is shown that, for any fixed dimension d, the linear programming problem with n inequality constraints can be solved on a probabilistic CRCW PRAM (concurrent-read-concurrent-write parallel random-access machine) with O(n) processors almost surely in constant time. The algorithm always finds the correct solution. With nd/log2d processors, the probability that the algorithm will not finish within O(d2log2d) time tends to zero exponentially with n.