1
$\begingroup$

Given a list of $n$ real numbers: $R=(r_1,r_2,\ldots,r_n)$ with $r_i < r_{i+1}$, and a target real number $t$, How can we find the subset of $R$ of size $k$ with a sum that best approximates $t$? I have no idea how to do this well for $k>2$ but I think that there should be an $n \log n$ algorithm.

This is what I know so far.

Case: $k=1$

Since the list is sorted you can find the $r_i$ that is closest to $t$ in $\mathcal{O}(\log n)$ time via binary search.

Case: $k = 2$

Start with $i = 1$ and $j = n$. While $i \le j$: if $(r_i+r_j) >t$ decrement $j$; else if $(r_i+r_j) < t$ increment $i$. Keep track of the best approximation as you go along. This is $\mathcal{O}(n)$

Case: $k=3$

Can we do better than $\mathcal{O}(n^2)$??

Case: $k>3$

??

$\endgroup$
  • $\begingroup$ By 'best approximate' you mean 'whose sum best approximates'? Since Subset Sum ( en.wikipedia.org/wiki/Subset_sum_problem ) is a special case of this ('can reach exactly' is the best approximation of all) this is at least NP-complete. $\endgroup$ – Steven Stadnicki Oct 7 '14 at 17:38
  • $\begingroup$ Yes. I changed the original. I'm not certain it is the Subset sum problem. Maybe it's more like a knapsack or a linear programming? I don't have enough experience to judge. $\endgroup$ – amcalde Oct 7 '14 at 17:40
  • $\begingroup$ It may be harder than Subset Sum, but it's certainly no easier; if you could solve your problem you could solve Subset Sum: just use any algorithm for this problem to find the subset that best approximates the target value, add the values of the subset found, and check whether they equal the target value. $\endgroup$ – Steven Stadnicki Oct 7 '14 at 17:42
  • $\begingroup$ Wait, but. For Subset Sum we are looking for ANY subset size. Here the sizes are fixed. For example it's easy for $k < 3$. I'm interested in specific $k$ sized sets. $\endgroup$ – amcalde Oct 7 '14 at 17:43
  • $\begingroup$ Searching on Subset sum I came across 3SUM. This is probably equivalent to that for $k=3$. $\endgroup$ – amcalde Oct 7 '14 at 17:45
0
$\begingroup$

Apparently for general problems at $k=3$ the answer is: "No, we cannot do better than $\mathcal{O}(n^2)$." However for some structured problems you can do much better. I guess it really depends on the problem and is a topic of ongoing research.

For $k>3$ the only known result is that you can do $\Omega(n^{\textrm{ceiling}(k/2)})$

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.