0
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ Related: en.wikipedia.org/wiki/… $\endgroup$ Jul 17 at 1:59
  • $\begingroup$ Perhaps the R package 'penalized' may be useful. $\endgroup$ Jul 18 at 13:19
  • $\begingroup$ @YaakovBaruch, Could you please explain how adding a penalty can be used to solve this problem? $\endgroup$
    – legon
    Jul 18 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$ Jul 19 at 9:59
2
$\begingroup$

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.

$\endgroup$
2
  • $\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$
    – legon
    Jul 18 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 at 16:12

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.