1. We will be in Read Only mode (no new threads, replies, registration) for several hours as we migrate the forums to upgraded software.

Minimization problem

Discussion in 'Math' started by veritas, Apr 7, 2009.

  1. veritas

    Thread Starter Active Member

    Feb 7, 2008
    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.