Re: Can this be solved in polynomial time?
- From: daw@xxxxxxxxxxxxxxxxxxxxxxxx (David Wagner)
- Date: Fri, 13 Apr 2007 23:28:15 +0000 (UTC)
You have a set S of size N.
You are given M subsets of S.
Find K of the given subsets, so that their union is of maximal size.
Can this problem be solved efficiently? If so, how?
Is this homework? If not, I think I have a concise answer (though I
haven't checked my answer carefully), but if it is, I don't want to
disrupt the learning process -- you can only learn by doing.
If it's not homework, it looks it would make a nice homework problem,
by the way. I think I'll save this for future reference.
.
- Follow-Ups:
- Re: Can this be solved in polynomial time?
- From: Leo2157
- Re: Can this be solved in polynomial time?
- References:
- Can this be solved in polynomial time?
- From: Leo2157
- Can this be solved in polynomial time?
- Prev by Date: Can this be solved in polynomial time?
- Next by Date: Re: Can this be solved in polynomial time?
- Previous by thread: Can this be solved in polynomial time?
- Next by thread: Re: Can this be solved in polynomial time?
- Index(es):
Relevant Pages
|
