Parallel linear programming in fixed dimension almost surely in constant time

1 March 1994

journal article
Published by Association for Computing Machinery (ACM) in Journal of the ACM

Vol. 41 (2) , 422-434
https://doi.org/10.1145/174652.174661

Abstract

For any fixed 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 finds the correct solution. With nd /log ² d processors, the probability that the algorithm will not finish within O ( d ² log ² d ) time tends to zero exponentially with n . — Authors' Abstract

Keywords

This publication has 9 references indexed in Scilit:

Linear Programming with Two Variables Per Inequality in Poly-Log Time
SIAM Journal on Computing, 1990
A randomized algorithm for fixed-dimensional linear programming
Mathematical Programming, 1989
A Las Vegas algorithm for linear programming when the dimension is small
Published by Institute of Electrical and Electronics Engineers (IEEE) ,1988
On a Multidimensional Search Technique and Its Application to the Euclidean One-Centre Problem
SIAM Journal on Computing, 1986
Linear programming in O(n × 3d) time
Information Processing Letters, 1986
Linear Programming in Linear Time When the Dimension Is Fixed
Journal of the ACM, 1984
Fast parallel matrix and GCD computations
Information and Control, 1982
Parallelism in Comparison Problems
SIAM Journal on Computing, 1975
A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
The Annals of Mathematical Statistics, 1952