Parallel Linear Programming in Fixed Dimension Almost Surely in Constant Time

Noga Alon, Nimrod Megiddo

Research output: Contribution to journalArticlepeer-review

17 Scopus citations


For any fixed dimension d, thelinear programming problem with ninequality constraints can be solved on a probabilistic CRCW PRAM withO1994processors almost surely in constant time. The algorithm always findsthe correct solution. Withnd/log2dprocessors, the probability that the algorithm will not finish withinO(d2log2dtime tends to zero exponentially withn.

Original languageEnglish (US)
Pages (from-to)422-434
Number of pages13
JournalJournal of the ACM (JACM)
Issue number2
StatePublished - Jan 3 1994
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Control and Systems Engineering
  • Information Systems
  • Hardware and Architecture
  • Artificial Intelligence


  • Computational geometry
  • linear programming
  • multidimensional search
  • parallel computation
  • probabilistic computation


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