# Minimization problem

forkedknight
Science 08 Apr '09 01:02
1. forkedknight
Defend the Universe
08 Apr '09 01:02
I have a minimization problem I need to solve as accurately as possible. I think it's NP-complete, but not entirely sure. I'd like to know if anyone has better ideas for solving it than I have, since my solution is O(2^n) time, and that's not acceptable.

I have n vectors, each of which can be represented with a k-bit binary number. Each vector has a "weight" of w

I need to select vectors such that the result of an AND between all of the vectors meets a maximum density (there is a max number of 1's in the result) while minimizing w.

The ideal solution would be to build a binary tree of the vectors such that each leaf represents one possibility of included/excluded vectors and the sum of w for the included vectors. The problem is that building this binary tree takes O(2^n) time.

Is there some way to combine the density of each vector with its weight to come up with a combined ranking of each vector? Feel free to ask for clarification if the problem is unclear.
2. forkedknight
Defend the Universe
08 Apr '09 01:09
suggestions for reducing k and n are also welcome. The initial value for k is in the 10,000s, and the value for n is in the hundreds.
3. forkedknight
Defend the Universe
08 Apr '09 01:11
And I realized I should probably have posted this in the Posers and Puzzlers forum. Can it be moved?
4. Palynka
Upward Spiral
09 Apr '09 08:01
What about using penalization techniques? Your problem sounds roughly like a minimax problem.