Sen, Sandeep (1990) Finding an approximate median with high probability in constant parallel time Information Processing Letters, 34 (2). pp. 77-80. ISSN 0020-0190
Full text not available from this repository.
Official URL: http://www.sciencedirect.com/science/article/pii/0...
Related URL: http://dx.doi.org/10.1016/0020-0190(90)90140-S
Abstract
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.
| Item Type: | Article |
|---|---|
| Source: | Copyright of this article belongs to Elsevier Science. |
| Keywords: | Analysis of Algorithms; Combinatorial Problems; Computational Complexity |
| ID Code: | 53422 |
| Deposited On: | 08 Aug 2011 12:08 |
| Last Modified: | 08 Aug 2011 12:08 |
Repository Staff Only: item control page
