Parallel linear programming in fixed dimension almost surely in constant time
- 4 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 574-582 vol.2
- https://doi.org/10.1109/fscs.1990.89578
Abstract
It is shown that, for any fixed dimension d, the linear programming problem with n inequality constraints can be solvent 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/log/sup 2/d processors, the probability that the algorithm will not finish within O(d/sup 2/log/sup 2/d) time tends to zero exponentially with n.Keywords
This publication has 6 references indexed in Scilit:
- Partition trees for triangle counting and other range searching problemsPublished by Association for Computing Machinery (ACM) ,1988
- A Las Vegas algorithm for linear programming when the dimension is smallPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1988
- Fast parallel matrix and GCD computationsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1982
- A fast probabilistic parallel sorting algorithmPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1981
- Parallelism in Comparison ProblemsSIAM Journal on Computing, 1975
- A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of ObservationsThe Annals of Mathematical Statistics, 1952