1
$\begingroup$

I have the following problem:

Given a matrix with n rows and m columns. Some elements of the matrix are unavailable. For each column, you have a set containing a number of zeros and ones which must be distributed over the available elements in that column. The total number of zeros and ones in a set is equal to the number of available elements in the corresponding column. The question is: How should the values of the sets be distributed over the elements in the corresponding colum, such that the number of rows for which the total number of ones is less than 20% of the available elements in that row, is minimized.

Does someone knows a similar problem which has a polynomial time algorithm solving the problem to optimality, or knows a polynomial time algorithm solving the problem to optimality (if it exists)?

$\endgroup$
  • $\begingroup$ To me this sounds like the typical case of a problem that can only be solved with backtracking, and thus should be NP. $\endgroup$ – Wolfgang Bangerth Feb 24 '16 at 23:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.