Finding an approximate median with high probability in constant parallel time

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