Hang-Yip Liu, Steffen Schulze, et al.
Proceedings of SPIE - The International Society for Optical Engineering
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((loglog 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((loglog n)d+c), where c is an absolute constant.
Hang-Yip Liu, Steffen Schulze, et al.
Proceedings of SPIE - The International Society for Optical Engineering
Preeti Malakar, Thomas George, et al.
SC 2012
Kaoutar El Maghraoui, Gokul Kandiraju, et al.
WOSP/SIPEW 2010
Elizabeth A. Sholler, Frederick M. Meyer, et al.
SPIE AeroSense 1997