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$
  • $\begingroup$ We don't expect randomized algorithms to be able to solve NP-hard problems. $\endgroup$ – Yuval Filmus Sep 28 '17 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 '17 at 11:18
  • 2
    $\begingroup$ Round the numbers and then use dynamic programming. ​ ​ $\endgroup$ – user12859 Sep 28 '17 at 11:20
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, privacy policy and cookie policy

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