Please turn on javascript in your browser to play chess.
Science Forum

Science Forum

  1. Standard member 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. Standard member 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. Standard member 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. Standard member Palynka
    Upward Spiral
    09 Apr '09 08:01
    What about using penalization techniques? Your problem sounds roughly like a minimax problem.