Header menu link for other important links
Finding an approximate median with high probability in constant parallel time
Published in
Volume: 34
Issue: 2
Pages: 77 - 80
Given n elements from a totally ordered set we outline a method for choosing an element whose rank is γn for some 0 <γ<1 where γ is independent of n. The algorithm executes in constant time in a CRCW PRAM model using a linear number of processors and succeeds with probability 1 - n-c for any c>0. © 1990.
About the journal
Published in
Open Access
Impact factor