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$.

  • $\begingroup$ Well, how about trying to prove it? $\endgroup$ – Yuval Filmus May 11 '18 at 20:24
  • $\begingroup$ I have tried, not succeeded. $\endgroup$ – user3563894 May 11 '18 at 21:54
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus May 11 '18 at 21:55
  • $\begingroup$ 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... $\endgroup$ – user3563894 May 11 '18 at 22:22
  • 1
    $\begingroup$ 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. $\endgroup$ – gnasher729 May 12 '18 at 14:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.