A Deterministic ${\operatorname{Poly}}(\log \log N)$-Time N -Processor Algorithm for Linear Programming in Fixed Dimension
Miklós Ajtai, Nimrod Megiddo · SIAM Journal on Computing · 1996
It is shown that for any fixed number of variables, linear-programming problems with n linear inequalities can be solved deterministically by n parallel processors in sublogarithmic time. The parallel time bound (counting only the arithmetic operations) is $O((\log \log n)^d )$, where d is the number of variables. In the one-dimensional case, this bound is optimal. If we take into account the operations needed for processor allocation, the time bound is $O((\log \log n)^{d + c} )$, where c is an absolute constant.