Choose the signs of vectors as to maximize modulus of their sum.

[sodemus]

Hi,

I have a fairly simple problem which but I'm not sure if it should rather be in a computer science forum for algorithms or something.

Given n vectors, how do you choose the sign of each vector as to maximize the modulus of the sum of the vectors?

Sure you could go through all 2^n combinations, but that's not necessarily the most efficient way (really, you only need to go through 2^(n-1) since the second half is just negative the first half, but still). I can't figure out what all the dependencies are.

 

[Lord Crc]

I'm assuming that by "sign of each vector" you mean if you should add or subtract that vector from the accumulated/summed vector, and that by modulus you mean the length.

My immediate thought was that you don't want to go "backwards". So if the inner product between the summed vector and the next vector is negative, subtract the vector, otherwise add it.

Of course, this might be just silly.

 

[sodemus]

Thanks for your reply and yes, you got the problem right!

Well, that was my first thought as well but I didn't think it actually leads to global maximum/minimum since that assumes knowledge of how the 2 first vectors would contribute to the final sum. Well, perhaps, since the sign of the resulting vector actually is arbitrary. But I think the final sum is only non-unique to one sign (two combinations) and the sum of the first two vectors are non-unique to two signs (4 combinations)...

Any thoughts are greatly appreciated!