# Minimise simultaneous equation remainder

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?

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.

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