# An approximation for the sum of k largest elements of n-sorted arrays?

Suppose we want to find the sum of the $k$ largest elements of $n$-sorted arrays. All arrays are containing $k$ elements.

All elements are between 0 and 1, and the the sum of all elements in array $i$ equals to $S_i$.

Instead of using a min-heap to find the $k$ largest elements (and thus, deriving the sum of the $k$ largest elements), one way for approximating the sum is to select the $k \cdot \frac{S_i} { {\sum_{i=1}^n} S_i}$ largest elements from array $i$.

We assume that $k \cdot \frac{S_i} { {\sum_{i=1}^n} S_i}$ is an integer, for every $i$.

Is the above algorithm is a constant-factor approximation algorithm? I think it is 0.5-approximation algorithm, but not sure yet.

Note that if the arrays have arbitrarily array sizes, then the claim is not true. For example, if there are $n=2$ arrays, one with $k$ elements equal to $1$, and the other with $k \cdot t^2$ elements of $1/t$, then while the sum of the $k$ largest elements is equal to $k$, the approximation will approach to $0$, as $t$ approaches to infinity. This why we assume that the array sizes are both equal to $k$.

• Well, how about trying to prove it? – Yuval Filmus May 11 '18 at 20:24
• I have tried, not succeeded. – user3563894 May 11 '18 at 21:54
• Have you tried easier cases, such as small $k$ or $n$? You can start with $k=1$, $k=2$, $n=1$, $n=2$, and so on. – Yuval Filmus May 11 '18 at 21:55
• Of course! I first tried to disproved the claim, by giving counter examples, but not succeed. However, for k=1,2 the claim holds. As well as for n=1. For n=2, I am not sure yet... – user3563894 May 11 '18 at 22:22
• With constant array size, the solution can still be arbitrarily bad. Let n = 2k. k arrays with one element = 1, 99 elements = 0, S = 1. k arrays with 100 elements = 0.1, S = 10. You will pick lots of the 0.1 elements. I saw you changed the number of elements to k: Still arbitrarily bad if k is large. – gnasher729 May 12 '18 at 14:22