Fast and optimal parallel multidimensional search in PRAMs with applications to linear programming and related problems

Abstract

We describe a deterministic parallel algorithm for linear programming in fixed dimension d that takes poly(log log n) time in the common concurrent read 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−1n) 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) algorithms for smallest enclosing sphere and approximate ham-sandwich cuts and an O(log n) time work-optimal algorithm for exact ham-sandwich cuts of separable point sets. For these problems, in particular for fixed-dimensional linear programming, o(log n) time efficient deterministic PRAM algorithms were not known until very recently.