1
$\begingroup$

Basically, I need to solve the multivariate case of the "closest subsequence sum to a given value K" problem, which is solved with dynamic programming as far as I understand. Let's say I have M rows of integer data.

A = [
[a11, a12, .., a1n], 
...
[ai1, ai2, .., ain],
...
[am1, am2, .., amn]
]

And I have a target vector K: K = [k1, .., kn]

In other words, I need to approximately solve the following system of linear equations:

w1*a11 + .. + wm*am1 = k1
...
w1*a1n + .. + wm*amn = kn

Where w1..wn can only assume values on 0 and 1, so it feels like a case of diophantine equations of sorts. I can't quite come up with a solution yet.

Another constraint is to have the closest subsequence of a fixed size, i.e. w1+ ... + wm = S. For example, I have 10000 rows and I want to find the 300 rows the sum of which will give me something close to my target vector K.

$\endgroup$

1 Answer 1

0
$\begingroup$

This can be formulated as an instance of the closest vector problem in a lattice.

In particular, replace the vector $(a_{i1},\dots,a_{in})$ with the vector $(a_{i1},\dots,a_{in},c,0,0,\dots,K,0,\dots,0)$, where the $K$ is in the $i$th position, $K$ is a large constant, and $c$ is a small constant. Let the target vector be $(k_1,\dots,k_n,cS,0,0,\dots,0)$. Now look for the closest vector to the target, in the lattice spanned by the other vectors.

There are a number of algorithms for the closest vector problem, including using LLL lattice reduction to get an approximate solution.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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