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)ᵈ ), 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.
No takes yet. Share an insight, caveat, or question.
Ajtai et al. (1996) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: