Parallel linear programming in fixed dimension almost surely in constant time
| Author(s) : | Nimrod Megiddo Noga Alon, |
| Publisher : | N/A |
| Publication Date : | 1990 |
| ISSN : | N/A |
| Abstract : | Abstract. For any xed dimension d, the linear programming problem with n inequality constraints can be solved on a probabilistic CRCW PRAM with O(n) processors almost surely in constant time. The algorithm always nds the correct solution. With nd = log 2 d processors, the probability that the algorithm will not nish within O(d 2 log 2 d) time tends to zero exponentially with n. 1., |