Re: Can this be solved in polynomial time?
On Apr 14, 2:28 am, d...@xxxxxxxxxxxxxxxxxxxxxxxx (David Wagner)
wrote:
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.
This is not homework. It is a part of a larger algorithm I am writing
for a program I am working on.
I need a solution as efficient as possible, but any polynomial
solution will be a good starting point.
You are most welcome to use it as homework.
.
Relevant Pages
- Re: Can this be solved in polynomial time?
... Find K of the given subsets, so that their union is of maximal size. ... disrupt the learning process -- you can only learn by doing. ... If it's not homework, it looks it would make a nice homework problem, ... I think I'll save this for future reference. ...
(comp.theory) - Re: I hate homework!
... verbally, writing is a whole different beast, as many can attest. ... or maybe even first grade maybe, but second graders should be able to do it. ... So that even mathematics is demanding of ... the ideal homework situation varies greatly. ...
(misc.kids) - Re: I hate homework!
... verbally, writing is a whole different beast, as many can attest. ... write-out x times assignment. ... Considering the different life-styles like kids with nannies and highly-educationally focused parents to kids who have very young parents on drugs who live in shelters, the ideal homework situation varies greatly. ...
(misc.kids) - Re: Homework for a 5 year old - how much involvement needed.
... Sure, offer suggestions and alternatives, and present things in different ways in class when you are responsible for teaching all the kids en masse, but homework is individual. ... At the beginning of the school year, send home a handout with suggestions on various techniques for learning spelling words. ... was an assignment that had them working on spelling, creativity, and sentence structure all at one time. ... If Penny's daughter has trouble in creative writing, it might be a good thing if she got small doses of it in other parts of her homework. ...
(misc.kids) - Re: I hate homework!
... Though your child can form complicated sentences verbally, writing is a whole different beast, as many can attest. ... I still don't think 20 sentences is too much for second grade, if he doesn't have much more than that as homework. ... So that even mathematics is demanding of ... Considering the different life-styles like kids with nannies and highly-educationally focused parents to kids who have very young parents on drugs who live in shelters, the ideal homework situation varies greatly. ...
(misc.kids) |
|
