Arnold L. Rosenberg
Journal of the ACM
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.
Arnold L. Rosenberg
Journal of the ACM
Benjamin N. Grosof
AAAI-SS 1993
Shipra Agrawal, Nimrod Megiddo, et al.
Economics Letters
George Saon
SLT 2014