John R. Kender, Rick Kjeldsen
IEEE Transactions on Pattern Analysis and Machine Intelligence
For any fixed dimension d, thelinear programming problem with ninequality constraints can be solved on a probabilistic CRCW PRAM withO1994processors almost surely in constant time. The algorithm always findsthe correct solution. Withnd/log2dprocessors, the probability that the algorithm will not finish withinO(d2log2dtime tends to zero exponentially withn. © 1994, ACM. All rights reserved.