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.
$\begingroup$
$\endgroup$
4
-
1$\begingroup$ Related: en.wikipedia.org/wiki/… $\endgroup$– Steve HuntsmanJul 17, 2021 at 1:59
-
$\begingroup$ Perhaps the R package 'penalized' may be useful. $\endgroup$– Yaakov BaruchJul 18, 2021 at 13:19
-
$\begingroup$ @YaakovBaruch, Could you please explain how adding a penalty can be used to solve this problem? $\endgroup$– legonJul 18, 2021 at 15:32
-
$\begingroup$ 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$. $\endgroup$– Yaakov BaruchJul 19, 2021 at 9:59
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
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.
On the practical side, there exist a number of software packages for solving CVP - e.g., see answers to this MO question.
answered Jul 17, 2021 at 2:43
-
$\begingroup$ Thank you for your thoughtful answer! After some reading about CVP, it seems to me that in full generality, this problem cannot be solved efficiently (the running time scales exponentially in dimension). Is there any probabilistic model for the lattice points for which the problem can be solved in polynomial time? $\endgroup$– legonJul 18, 2021 at 15:26
-
$\begingroup$ @legon: I'm not sure about probabilistic models, but there exist efficient approximate algorithms (e.g., based on LLL) for solving CVP. $\endgroup$ Jul 18, 2021 at 16:12