PARALLEL LINEAR-PROGRAMMING IN FIXED DIMENSION ALMOST SURELY IN CONSTANT-TIME

Authors
ALON N MEGIDDO N
Citation
N. Alon et N. Megiddo, PARALLEL LINEAR-PROGRAMMING IN FIXED DIMENSION ALMOST SURELY IN CONSTANT-TIME, Journal of the Association for Computing Machinery, 41(2), 1994, pp. 422-434
Citations number
14
Categorie Soggetti
Computer Sciences","Computer Science Hardware & Architecture
Journal title
Journal of the Association for Computing Machinery
ISSN journal
00045411 → ACNP
Volume
41
Issue
2
Year of publication
1994
Pages
422 - 434
Database
ISI
SICI code
Abstract
For any fixed dimension d, the linear programming problem with n inequ ality constraints can be solved on a probabilistic CRCW PRAM 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 exp onentially with n.