3
$\begingroup$

I have a large matrix that is populated with a list of people, and a 1 or 0 as to whether or not they have a particular flag. A person can have one or more flags, or none at all. For example:

$$ \begin{matrix} Person & Flag1 & Flag2 & Flag3 \\ John & 1 & 0 & 0\\ Mary & 1 & 0 & 1\\ Luke & 0 & 1 & 0\\ Paul & 0 & 0 & 0\\ \end{matrix} $$

I can clear only one flag at a time (i.e. set a column to 0 for the whole population), and each requires about the same amount of work. My goal is to clean (a clean person has no flags) a certain percentage, p, of the population. How can I (besides trial and error) figure out the most efficient flag clearing strategy?

EDIT: My second thought to this was to think of the problem from the opposite side, or "how many flags can I keep and still maintain a p clean percentage". For this, I'd iterate through combinations of the columns, and see which combinations left me with clean / total >= p, and choosing the combination with the largest amount of columns.

EDIT: Can someone prove that there is an efficient solution? My gut tells me it could definitely be np-hard but I can't find a way to prove either a reduction or a poly-time algorithm.

  • 0
    So "clearing a flag" is just setting an entire column to zero, and you can only set one column to zero at a time. A "clean" person is associate with a row whose row sums to zero. You're then asking "what is the fewest number of operations to perform" to achieve $p>= k/n$ rows with zero row sums, correct?2012-08-21
  • 0
    exactly. my initial thought was calculating p for each combination of flags (thinking about it not as clearing flags, but keeping them), and picking the combination with the largest # of columns, but i was curious as to if there was an easier and faster way.2012-08-21

1 Answers 1