2

I am wondering if there is a known algorithm for solving the following.

Data: There is a number of sets containing items. An item can be a member of more than one set.

Aim: return the minimum number of sets which between them contain all of the items, and avoid returning duplicate items as much as possible. For example:

  • Set 1: a
  • Set 2: a, b
  • Set 3: b, c

For this I would want to return sets 1 and 3. This is the fewest sets which combined contain at least 1 copy of all the items and duplicate items are kept to a minimum.

BTW - I will be looking to implement this in C#.

4
  • 1
    I'm fairly certain that this is another variation of the knapsack problem.
    – user40980
    Nov 18, 2014 at 6:19
  • 3
    Did you read this Wikipedia article? en.wikipedia.org/wiki/Set_cover_problem
    – Doc Brown
    Nov 18, 2014 at 6:20
  • Those both look interesting. Thanks! I suspect that the Set cover problem page is what I am looking for. Nov 18, 2014 at 6:30
  • That might be a good talk for codegolf.stackexchange.com :)
    – Knerd
    Nov 18, 2014 at 8:42

1 Answer 1

2

Your problem is, I believe, NP-complete, so unless the number of sets you are dealing with is small, there isn't a guaranteed accurate solution that will run in a realistic time. You may plausibly be able to get accurate results by a global search (basically listing all possible combinations of sets and checking which one gives the best results) for up to about 20 sets, but not much larger problems than that.

Your requirement to minimize duplication makes it slightly different to the set cover problem as linked in the comments, and it may be that the approximate solution described in that article (essentially iterating the process of picking the choice that brings you closest to a solution until you have complete cover) doesn't work well enough for you as it entirely ignores your extra requirement.

If this is the case, I'd take an approach of using this algorithm to generate a first candidate solution, and then using simulated annealing in a similar manner to how it is applied to the traveling salesman problem as a final optimization step. I think this should result in something close to an optimal solution most of the time.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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