Parallel linear programming in fixed dimension almost surely inconstant time

摘要

It is shown that, for any fixed dimension d, the linearprogramming problem with n inequality constraints can besolvent on a probabilistic CRCW PRAM (concurrent-read-concurrent-writeparallel random-access machine) with O(n) processorsalmost surely in constant time. The algorithm always finds the correctsolution. With nd/log²d processors, theprobability that the algorithm will not finish within O(d²log²d) time tends to zeroexponentially with n