1
$\begingroup$

I'm not sure if this is the right place to ask, or what the right terminology to use is. The problem I have is this: I have a vector for example: v = [1,4,5,6,3,1,4,5,6,7,...7]

and I have a set of other vectors for example: a1 = [0,0,0,0,0,1,2,3,0,0,...0] a2 = [0,0,0,0,1,2,5,0,0,0,...0] a3 = [0,0,0,2,2,3,0,0,0,0,...0] a4 = [0,0,1,1,1,0,0,0,0,0,...0] ... an = [0,0,1,1,1,0,0,0,0,0,...0]

I want to find out what linear combination of the vectors is closest to v. I define the distance of two vectors to be the sum of the absolute differences of each of its elements. For example the distance between [1,2,3] and [2,2,2] is abs(1-2) + abs(2-2) + abs(3-2) = 2.

Does such an algorithm exist? If it doesn't exist, are there any algorithms that could get me close to a solution?

Ideally I would like an integer multiple of each vector, does such a solution exist with integer multiples?

$\endgroup$
2
$\begingroup$

This problem is an instance of linear programming.

If you allow fractional multiples then it can be solved in polynomial time using standard techniques for linear programming.

If you require integer multiples the problem is (strongly) $NP$-complete. There is a very easy reduction from 1-in-3-SAT. Let the dimension of the vectors be equal to the number of clauses, let the target vector be $(1,\ldots,1)$ and for every variabele create a vector $a_i$ that for each clause it appears in has a $1$ in that position (and a $0$ otherwise). You can achieve distance $0$ if and only if the formula is satisfiable.

$\endgroup$
  • 2
    $\begingroup$ I'd say a reduction from Subset Sum is more immediate. $\endgroup$ – Raphael May 27 '15 at 11:04
  • $\begingroup$ Can you point me in the direction of the "standard techniques for linear programming"? $\endgroup$ – dan May 27 '15 at 11:11
  • $\begingroup$ @dan Simplex Algorithm is the most practical technique. Strictly speaking it's not polynomial, but in practise it works very well. $\endgroup$ – Tom van der Zanden May 27 '15 at 11:12
  • $\begingroup$ @Raphael it is, but only yields weak hardness. $\endgroup$ – Tom van der Zanden May 27 '15 at 11:14

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.