# Finding a subset of vectors whose sum is close to a given vector

Given a set of vectors $$x_1,...,x_n\in\mathbb{R}^d$$ and a vector $$y$$, find a subset $$I\subset\{1,2,...,n\}$$ such that $$\|\sum_{i\in I} x_i-y\|$$ is as small as possible. Here $$\|.\|$$ can be any norm, and $$I$$ is not required to be the optimal set. This problem is closely related to the subset-sum and knapsack problems, but I only need an efficient algorithm for finding a reasonably good set $$I$$. Any relevant references are greatly appreciated.

• Related: en.wikipedia.org/wiki/… Jul 17 at 1:59
• Perhaps the R package 'penalized' may be useful. Jul 18 at 13:19
• @YaakovBaruch, Could you please explain how adding a penalty can be used to solve this problem? Jul 18 at 15:32
• Sorry. I carelessly, completely misread the question. I was thinking of a finding hyperspaces of small dimension (generated by some $x_i$'s) that come close to $y$. Jul 19 at 9:59

This can be reduced to the closest vector problem by appending each $$x_i$$ with $$2M\cdot e_i$$ resulting in a $$(d+n)$$-dimesional vector $$x'_i$$, and appending $$y$$ with $$(M,M,\dots,M)$$ resulting in a $$(d+n)$$-dimesional vector $$y'$$, If constant $$M$$ is large enough, then the solution to CVP for $$y'$$ in the lattice spanned by $$x'_i$$ will have 0-1 coefficients and deliver a solution to the original problem.