Me. Dyer et S. Sen, Fast and optimal parallel multidimensional search in prams with applications to linear programming and related problems, SIAM J COMP, 30(5), 2000, pp. 1443-1461
We describe a deterministic parallel algorithm for linear programming in fi
xed dimension d that takes poly(log log n) time in the common concurrent re
ad concurrent write ( CRCW) PRAM model and does optimal O (n) work. In the
exclusive read exclusive write (EREW) model, the algorithm runs in O ( log
n . log log(d-1) n) time. Our algorithm is based on multidimensional search
and effective use of approximation algorithms to speed up the basic search
in the CRCW model. Our method also yields very fast poly( log log n) algor
ithms for smallest enclosing sphere and approximate ham-sandwich cuts and a
n O (log n) time work-optimal algorithm for exact ham-sandwich cuts of sepa
rable point sets. For these problems, in particular for fixed-dimensional l
inear programming, o(log n) time efficient deterministic PRAM algorithms we
re not known until very recently.