A Deterministic Poly(log log N)-Time N-Processor Algorithm for Linear Programming in Fixed Dimension

It is shown that for any fixed number of variables, the linear programming problems with n linear inequalities can be solved deterministically by n parallel processors in sub-logarithmic time. The parallel time bound is O((log log n ) d ) where d is the number of variables. In the one-dimensional case this bound is optimal.

Authors

• Miklós Ajtai
• Nimrod Megiddo

Keywords

No keywords are indexed for this paper.