Finding minimum subset of objects with attributes.

Question

I have algorithmic problem. I don't know how to solve it. Maybe someone can help me?

I have objects. Each object has the same features. It could be illustrated in table:

                 Feature1    Feature2    Feature3   Feature4
      Object1       1           0           1          1

      Object2       0           0           0          1

      Object3       0           1           1          1

      Object4       0           1           0          0

Now I want to find all minimum subsets of objects. Each subset should have at least one value "1" for each feature. For table above results are two subsets: {Object1, Object3} and {Object1, Object4}. I cannot generate all possible subsets because it could take too much time.

Answer 1

This is exactly the set cover problem. The problem is NP-hard so if you need the exact minimum, generating all possible subsets would not be so much worse than other solutions in time.

But there are some polynomial time approximation algorithms. See the Wikipedia page for detail. The "best" is the greedy algorithm, which runs like this:

1. Initialize the unimplemented features as {Feature1, Feature2, Feature3, ...}
2. Select the object which implements most unimplemented features.
3. Repeat 2 until all features are implemented.

Answer 2

You can reduce the problem by including by necessity all objects that are the sole possessor of a given feature (or features). Object1 is the only one that has Feature1 so you know you need that one in your solution.