Parallel linear programming in fixed dimension almost surely in constant time

Noga Alon, Nimrod Megiddo

Research output: Contribution to journalConference article

20 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)574-582
Number of pages9
JournalAnnual Symposium on Foundations of Computer Science - Proceedings
Volume2
StatePublished - Dec 1 1990
Externally publishedYes
EventProceedings of the 31st Annual Symposium on Foundations of Computer Science - St. Louis, MO, USA
Duration: Oct 22 1990Oct 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