On: Algorithms, A Dropbox Challenge and Dynamic Progra...

[NY_USA_Hacker]

So, for the problem, we are given some positive integer n and, for i = 1, 2, ..., n, numbers a(i).

So, we seek x(i) to solve

     min ( x(1) a(1) + x(2) a(2) + ... + x(n) a(n) )^2

     x(1) + x(2) + ... + x(n) >= 0

     subject to x(i) = 0, 1

So this is a 0-1 integer quadratic program with one linear constraint.

So for a reasonably practical solution, omit the 0-1 constraint and attack the problem as just a quadratic program.

Then for the 0-1 constraint, do standard branch and bound.