Timeline for Covering set problem
Current License: CC BY-SA 3.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 15, 2012 at 23:27 | comment | added | Gerhard Paseman | Now if we rewrite his question, provide a guessing parameter m, and ask about determining whether a hitting set Y of size at most m exists, that is an interesting and related question, and your remarks above would apply to estimating m. Agaon, I think David's question is sufficiently different from this hypothetical rewrite. In the comments above, just the existence of an unparameterized Y is mentioned, which for us should be easy to establish. Gerhard "Now I Am Really Done" Paseman, 2012.04.15 | |
| Apr 15, 2012 at 23:16 | comment | added | Gerhard Paseman | Even though he may want a function f (and not a proof that f works) that does the right thing, I think algorithmics will provide such an f. I know that for some functions g, algorithmics is used to find examples which are not bounded by g (My creaky memory suggests bin packing, something like first fit increasing and some threshhold like 11/9 which was one of the first appproximation results I learned, probably around the time I took Math 221.) Provocative as my comment was, my intent was to clarify, and let David correct me if needed. Gerhard "That's All For Right Now" Paseman, 2012.04.15 | |
| Apr 15, 2012 at 23:05 | comment | added | Gerhard Paseman | Along with Brendan, I believe David wants a nice function f of the parameters t,k and n that will say that any instance that satisfies the parameters will have a minimal hitting set of size at most f, and thus a hitting set of size exactly f. Nice is subjective, but for this problem we might agree that he wants one of better order than he stated with as few compositions and auxillary functions as possible, and I suspect he just cares about the order of f. Although I may be wrong in thinking this, I think he wants approximation results. Gerhard "And There Is Still More" Paseman, 2012.04.15 | |
| Apr 15, 2012 at 22:58 | comment | added | Gerhard Paseman | Even though in his comment David mentioned covering set, I believe he meant hitting set, as he does in the question when he mentions Y. Although he does not say t > 0, I think it is an interesting problem only if t > 0. With these as my belief set, I think the existence of a hitting set is trivial, by forming Y from a favored choice of an element from each of the X sets. (I have seen no restrictions on Y, just a desire for minimizing the size of Y.) Gerhard "But Wait, There is More" Paseman, 2012.04.15 | |
| Apr 15, 2012 at 18:49 | comment | added | JeffE | @Gerhard: I'm having trouble extracting your interpretation of the question from the written text. I misinterpreted the last sentence as "I am not concerned with an algorithm for finding Y, only for determining whether it exists...". | |
| Apr 15, 2012 at 13:39 | comment | added | Brendan McKay | @Gerhard: My understanding is that David wants a good upper bound on the minimum hitting set as a function only of $k,t,n$, not as a function of the actual sets presented. David, is that right? | |
| Apr 14, 2012 at 20:45 | comment | added | Gerhard Paseman | David Harris, I respectfully disagree with your comment. The existence of such a set is trivial; you are interested in good, or at least better than obvious, upper bounds on the size of such a set. A good part of algorithmics is in determining such bounds, and I think you will benefit most from approximation results, which JeffE might be able to provide. Even if you don't want to see how the result is made, I think you will be interested in the taste, which to me means you care at least about the output of the algorithmics process. Gerhard "But I've Been Wrong Before" Paseman, 2012.04.14 | |
| Apr 14, 2012 at 19:27 | comment | added | David Harris | As I said, I am not interested in algorithmics, only the existence of covering set. | |
| Apr 14, 2012 at 18:47 | comment | added | Gerhard Paseman | This shows that the size is hard to determine, not that it is hard to approximate. The question asked is whether O((n log k)/t) is the right order of magnitude, or is there something provably smaller. If you have approximation results or evem an example (well, family of examples) where Y has that order of magnitude, that would answer the question. Gerhard "Ask Me About System Design" Paseaman, 2012.04.14 | |
| Apr 14, 2012 at 18:14 | history | answered | JeffE | CC BY-SA 3.0 |