Parallel Linear Programming in Fixed Dimension Almost Surely in Constant Time

Noga Alon; Nimrod Megiddo

doi:10.1145/174652.174661

Parallel Linear Programming in Fixed Dimension Almost Surely in Constant Time

Noga Alon, Nimrod Megiddo

Research output: Contribution to journal › Article › peer-review

17 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/log²dprocessors, the probability that the algorithm will not finish withinO(d²log²dtime tends to zero exponentially withn.

Original language	English (US)
Pages (from-to)	422-434
Number of pages	13
Journal	Journal of the ACM (JACM)
Volume	41
Issue number	2
DOIs	https://doi.org/10.1145/174652.174661
State	Published - Jan 3 1994
Externally published	Yes

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

Access to Document

10.1145/174652.174661

Cite this

@article{b5589eeb321746e1abf4dd706db52be2,

title = "Parallel Linear Programming in Fixed Dimension Almost Surely in Constant Time",

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.",

keywords = "Computational geometry, linear programming, multidimensional search, parallel computation, probabilistic computation",

author = "Noga Alon and Nimrod Megiddo",

year = "1994",

month = jan,

day = "3",

doi = "10.1145/174652.174661",

language = "English (US)",

volume = "41",

pages = "422--434",

journal = "Journal of the ACM (JACM)",

issn = "0004-5411",

publisher = "Association for Computing Machinery (ACM)",

number = "2",

}

TY - JOUR

T1 - Parallel Linear Programming in Fixed Dimension Almost Surely in Constant Time

AU - Alon, Noga

AU - Megiddo, Nimrod

PY - 1994/1/3

Y1 - 1994/1/3

N2 - 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.

AB - 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.

KW - Computational geometry

KW - linear programming

KW - multidimensional search

KW - parallel computation

KW - probabilistic computation

UR - http://www.scopus.com/inward/record.url?scp=84976710685&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84976710685&partnerID=8YFLogxK

U2 - 10.1145/174652.174661

DO - 10.1145/174652.174661

M3 - Article

AN - SCOPUS:84976710685

SN - 0004-5411

VL - 41

SP - 422

EP - 434

JO - Journal of the ACM (JACM)

JF - Journal of the ACM (JACM)

IS - 2

ER -

Parallel Linear Programming in Fixed Dimension Almost Surely in Constant Time

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this