2
$\begingroup$

Let's say there is a set of $N$ real numbers, $x_i, i\in\{1,2,...,N\}$, and we would like to choose $n$ points out of them to get the sum of the chosen points as close as possible to a certain number, $y$, i.e. minimising $$ f(J) = \left[y - \sum_{j\in J}x_j \right]^2 s.t. ~J \subset \{1,2,...,N\} ~\mathrm{and}~ |J| = n $$ To get the exact solution, I think this is an $NP$ problem, so is there any random algorithm to find the (approximate) solution reasonably fast?

$\endgroup$
3
  • $\begingroup$ We don't expect randomized algorithms to be able to solve NP-hard problems. $\endgroup$ Sep 28, 2017 at 11:05
  • $\begingroup$ @YuvalFilmus I don't expect it to get the exact solution either. Approximate solution with reasonably low $f$ in a reasonable amount of time is acceptable. $\endgroup$
    – Firman
    Sep 28, 2017 at 11:18
  • 2
    $\begingroup$ Round the numbers and then use dynamic programming. ​ ​ $\endgroup$
    – user12859
    Sep 28, 2017 at 11:20

1 Answer 1

2
$\begingroup$

Round the $x_i$ into multiples of $(\epsilon/n) N$ (for a parameter $\epsilon > 0$ of your choice) which we will denote by $y_i$, and use dynamic programming to solve your problem for the $y_i$ in time $O(n^2N/\epsilon)$, coming up with a set $J$. Since $\sum_{j \in J} |x_j - y_j| \leq \epsilon N$, this will go you the correct answer up to an additive error of $\epsilon N$.

(Ricky Demer suggested the same solution in the comments to the post.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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