### 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/log^{2}d processors, the probability that the algorithm will not finish within O(d^{2}log^{2}d) time tends to zero exponentially with n.

Original language | English (US) |
---|---|

Pages (from-to) | 574-582 |

Number of pages | 9 |

Journal | Annual Symposium on Foundations of Computer Science - Proceedings |

Volume | 2 |

State | Published - Dec 1 1990 |

Externally published | Yes |

Event | Proceedings of the 31st Annual Symposium on Foundations of Computer Science - St. Louis, MO, USA Duration: Oct 22 1990 → Oct 24 1990 |

### All Science Journal Classification (ASJC) codes

- Hardware and Architecture

## Fingerprint Dive into the research topics of 'Parallel linear programming in fixed dimension almost surely in constant time'. Together they form a unique fingerprint.

## Cite this

Alon, N., & Megiddo, N. (1990). Parallel linear programming in fixed dimension almost surely in constant time.

*Annual Symposium on Foundations of Computer Science - Proceedings*,*2*, 574-582.