robcp (version 0.3.8)

kthPair: K-th largest element in a sum of sets.

Description

Selects the k-th largest element of X + Y, a sum of sets. X + Y denotes the set \(\{x + y | x \in X, y \in Y\}\).

Usage

kthPair(X, Y, k, k2 = NA)

Value

K-th largest value (numeric).

Arguments

X

Numeric vector.

Y

Numeric vector.

k

Index of element to be selected. Must be an integer and between 1 and the product of the lengths of x and y.

k2

Optional second index. k and k2 must be consecutive. Useful, if the number of elements of X + Y is even and the median is to be calculated.

Author

Sheila Görz

Details

A generalized version of the algorithm of Johnson and Mizoguchi (1978), where \(X\) and \(Y\) are allowed to be of different lengths. The optional argument k2 allows the computation of the mean of two consecutive value without running the algorithm twice.

References

Johnson, D. B., & Mizoguchi, T. (1978). Selecting the K-th Element in X+Y and X_1+X_2+ ... +X_m. SIAM Journal on Computing, 7(2), 147-153.

Examples

set.seed(1895)
x <- rnorm(100)
y <- runif(100)

kthPair(x, y, 5000)
kthPair(x, y, 5000, 5001)