Selecting the K th Element in $X + Y$ and $X_1 + X_2 + \cdots + X_m $
Donald Barton Johnson, Tetsuo Mizoguchi · SIAM Journal on Computing · 1978
An algorithm is given which selects the Kth element in $X + Y$ in $O(n\log n)$ time and $O(n)$ space, where $X + Y$ is the multiset $\{ x_i + y_j | x_i \in X\text{ and } y_j \in Y\} $ for $X = (x_1 ,x_2 , \cdots ,x_n )$ and $Y = (y_1 ,y_2 , \cdots ,y_n )$, n-tuples of real numbers. The results are extended to $\sum_{i = 1}^m {X_i } $ for $m > 2$. There is strong evidence that this more general problem is difficult if m and K may be selected arbitrarily. However, algorithms can be shown which are fast for small K and arbitrary m.