A deterministic poly(log log N)-time N-processor algorithm for linear programming in fixed dimension
Miklós Ajtai, Nimrod Megiddo · 1992
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.