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

  • Thread starter sodemus
  • Start date
  • #1
29
0

Main Question or Discussion Point

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.
 
Last edited:

Answers and Replies

  • #2
291
29
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.
 
  • #3
29
0
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!
 

Related Threads for: Choose the signs of vectors as to maximize modulus of their sum.

Replies
2
Views
10K
Replies
4
Views
487
Replies
1
Views
673
  • Last Post
Replies
7
Views
7K
Replies
8
Views
2K
Replies
4
Views
2K
Top