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

Authors
Citation
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
Citations number
35
Language
INGLESE
art.tipo
Article
Categorie Soggetti
Computer Science & Engineering
Journal title
SIAM JOURNAL ON COMPUTING
ISSN journal
0097-5397 → ACNP
Volume
30
Issue
5
Year of publication
2000
Pages
1443 - 1461
Database
ISI
SICI code
0097-5397(2000)30:5<1443:FAOPMS>2.0.ZU;2-M
Abstract
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.