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?
3
-
$\begingroup$ We don't expect randomized algorithms to be able to solve NP-hard problems. $\endgroup$– Yuval FilmusSep 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$– FirmanSep 28, 2017 at 11:18
-
2$\begingroup$ Round the numbers and then use dynamic programming. $\endgroup$– user12859Sep 28, 2017 at 11:20
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.)
answered Sep 28, 2017 at 11:22