Set Covering

We want to make a small committee to look into global warming, but we want to make sure all of the following 7 groups are represented: Women, Homosexuals, Jews, African Americans, Tall people, Native Americans, Republicans.

Mick F F F F F T F
Harvey F T T F T F T
Wilt F F F F T T F
Sue T T T F F T F
Barney F F F F T F F
Myrna T F T F F F T
Tiffany T F F T T T F

Minimal set cover: No one redundant. How solve this efficiently?

Minimum set cover: Smallest possible committee. How solve this efficiently?


next up previous
Next: Decision-Problem Version Up: NP-COMPLETE PROBLEMS Previous: NP-COMPLETE PROBLEMS