About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
FOCS 1990
Conference paper
Parallel linear programming in fixed dimension almost surely in constant time
Abstract
It is shown that, for any fixed dimension d, the linear programming problem with n inequality constraints can be solved 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/log2d processors, the probability that the algorithm will not finish within O(d2log2d) time tends to zero exponentially with n.