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 tried searching a bit for this but didn't come across it, it seems like it should be easier to find.

I'm trying to figure out if an algorithm exists for finding an optimum set, now to explain what I mean about this.

I'm looking for a set of sets which contains the least number of sets from the original set of sets, but contains all elements the universe of the original set covers.

I.E.

a = {1,2,3,4}
b = {2,3,4,5}
c = {3,4,5,6}
d = {5,6,7,8}

The optimum set would in the above case be:

optimum set = {a,d}

I can find this out by taking all of the sets and ensuring the universe has only one of each of them. I.E.

e = a U b U c U d

Then I take and do something like this (pardon if my syntax isnt quite up to par)

if e = {a} return {a}
if e = {b} return {b}
if e = {c} return {c}
if e = {d} return {d}
if e = {a,b} return {a,b}
if e = {a,c} return {a,c}
...
if e = {a,b,c,d} return {a,b,c,d}

My apologies if i'm not clear enough, I am a software engineer and ran into this problem. I was hoping that there would be perhaps some set operations which would result in what I'm looking for with minimal computation.

I currently am brute forcing a simplified version which is finding which sets are subsets of other sets, it's slow and I'm sure there is a faster way to do that but it's not so slow that I would need a better algorithm.

If this doesn't exist out there, are sets the right approach, or is there another branch of mathematics that might get me where I'm aiming for?

share|improve this question
1  
Not every question about sets is set theory. This is a question about algorithm design, and I'm not 100% sure that it even fits the topic of this site. –  Asaf Karagila Aug 14 '13 at 17:42
    
I guess I wasn't sure if there was an "operation" which would transform the set in which case I can code it up separately, if that makes sense, kind of like set a - set b gives you a new set, I wasn't sure if some equation (i.E. set a - set b + set c minus the univere) could solve the problem, which is why I asked here. –  onaclov2000 Aug 14 '13 at 17:44
1  
I think you are using "i.e." wrong. –  Asaf Karagila Aug 14 '13 at 18:00
    
From the sounds of it, the OP is looking for an algorithm to find a minimal subcover of a finite cover of a finite set by subsets. Is this correct? I'm sure this is something that's been considered in some context, but I suspect that context is indeed algorithm design. –  Branimir Ćaćić Aug 14 '13 at 18:08
    
I wasn't sure if an algorithm was required or if there was an operation. If no "operation" then either an algorithm, or at least a name for what I was trying to do, (hoping to at least find an algorithm), from the answer below, I was able to find some information that helped me get going. and Thank you Asaf Karagila for pointing out that I used I.E wrong, I'm sure you weren't able to understand what my intention was in my comment, so I guess I can spell it out for you, in the above case I was using I.E. = For example, sorry for the confusion –  onaclov2000 Aug 15 '13 at 11:27
add comment

1 Answer

up vote 3 down vote accepted

Wikipedia calls this the this is the set cover problem.

According to the wiki, there is no "efficient" algorithm to solve it, and there isn't even a "good" approximation algorithm to finding something that is nearly the smallest solution.

Of course, special sorts of problems can have efficient algorithms. And even "inefficient" algorithms can solve small cases reasonably fast. Hopefully the wiki or the buzzword can lead you to existing algorithms.

Otherwise, you might simply try a programming forum with help trying to write a well-optimized brute force solution. (e.g. using bitsets and bit twiddling)

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.