Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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? –  Arkamis Aug 21 '12 at 18:34
    
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. –  Christopher Howes Aug 21 '12 at 18:50
add comment

1 Answer

Begin by looking at row sums. The row sum at any step is equal to the minimum number of operations to "clean" that individual. Consider rows with equal sums first. Take the column sum of just those rows. The most "efficient" operation would be to clear the column with the highest column sum among rows with equal sums -- the most bang for the buck. Repeat until desired $p$ is matched as closely as possible. Note that because you have $n$ individuals, $k$ of whom are clean, the percentage of clean individuals is a rational number $k/n$. As such, not every percentage is possible -- so you may need to determine success as having $k/n = \sup \left\{ x/n | x/n < p,\ x \in \Bbb N\right\}$, or similarly for the converse.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.