Parallel Linear Programming in Fixed Dimension Almost Surely in Constant Time

Noga Alon, Nimrod Megiddo

Research output: Contribution to journalArticlepeer-review

18 Scopus citations

Abstract

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)
Volume41
Issue number2
DOIs
StatePublished - Jan 3 1994
Externally publishedYes

All Science Journal Classification (ASJC) codes

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

Keywords

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

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