A parallel selection algorithm

The problem of selecting thekth largest or smallest element of {x_i+y_j|x_i X andy_j Y i,j} whereX=(x₁,x₂, ..,x_n) andY=(y₁,y₂, ...,y_n) are two arrays ofn elements each, is considered. Certain improvements to an existing algorithm are proposed. An algorithm requiringO(logk·logn) units of time on a Shared Memory Model of a parallel computer havingO(n^1+1/) processors is presented where is a pre-assigned constant lying between 1 and 2.