Parallel linear programming in fixed dimension almost surely in constant time

摘要

It is shown that, for any fixed dimension d, the linear programming problem with n inequality constraints can be solvent 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/log/sup 2/d processors, the probability that the algorithm will not finish within O(d/sup 2/log/sup 2/d) time tends to zero exponentially with n.