Parallel linear programming in fixed dimension almost surely in constant time

Noga Alon; Nimrod Megiddo

Parallel linear programming in fixed dimension almost surely in constant time

Noga Alon, Nimrod Megiddo

Research output: Contribution to journal › Conference article › peer-review

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²d processors, the probability that the algorithm will not finish within O(d²log²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 - 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

Cite this

@article{7676f6213a944a619122cc0d6d87a0ed,

title = "Parallel linear programming in fixed dimension almost surely in constant time",

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

author = "Noga Alon and Nimrod Megiddo",

year = "1990",

language = "English (US)",

volume = "2",

pages = "574--582",

journal = "Annual Symposium on Foundations of Computer Science - Proceedings",

issn = "0272-5428",

note = "Proceedings of the 31st Annual Symposium on Foundations of Computer Science ; Conference date: 22-10-1990 Through 24-10-1990",

}

TY - JOUR

T1 - Parallel linear programming in fixed dimension almost surely in constant time

AU - Alon, Noga

AU - Megiddo, Nimrod

PY - 1990

Y1 - 1990

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

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

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

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

M3 - Conference article

AN - SCOPUS:0025530767

SN - 0272-5428

VL - 2

SP - 574

EP - 582

JO - Annual Symposium on Foundations of Computer Science - Proceedings

JF - Annual Symposium on Foundations of Computer Science - Proceedings

T2 - Proceedings of the 31st Annual Symposium on Foundations of Computer Science

Y2 - 22 October 1990 through 24 October 1990

ER -

Parallel linear programming in fixed dimension almost surely in constant time

Abstract

All Science Journal Classification (ASJC) codes

Other files and links

Fingerprint

Cite this