1. Standard memberforkedknight
    Defend the Universe
    127.0.0.1
    Joined
    18 Dec '03
    Moves
    15977
    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 memberforkedknight
    Defend the Universe
    127.0.0.1
    Joined
    18 Dec '03
    Moves
    15977
    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 memberforkedknight
    Defend the Universe
    127.0.0.1
    Joined
    18 Dec '03
    Moves
    15977
    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 memberPalynka
    Upward Spiral
    Halfway
    Joined
    02 Aug '04
    Moves
    8702
    09 Apr '09 08:01
    What about using penalization techniques? Your problem sounds roughly like a minimax problem.
Back to Top