Re: Help: How to combine all 4's into least 6's- Is there a way to calculate what the minimum of 6's will be?

[mensanator@xxxxxxx]
> ...
> My first algorithm got 21 as the smallest covering set. It's possible
> it could do better if I changed some things around to allow more
> cases to be checked. I'll play around with it this weekend.

FYI, I wrote a little backtracking Python program using a greedy ordering
heuristic: at each step, sort the 6-sets that haven't yet been used, in
decreasing order of the number of 4-sets still remaining (== weren't covered
by a previous 6-set selection) covered by the 6-set. Wow -- that's a
mouthful ;-). IOW, of all the choices available at each step, try those
that "cross off" (cover) a maximal number of remaining 4-sets first, and
those that cross off a minimal number last, recursing after each choice.
There's no point trying a 6-set all of whose 4-subsets have already been
crossed off, and that allows for significant pruning of the implicit search
tree. Subsets were represented as bit vectors (integers), and to save a lot
of repeated computation a setup step created a dict mapping each 6-set to a
set containing the 15 4-sets it covers.

Anyway, that worked about as expected: it found a covering using 20 6-sets
in a fraction of a second, but looks like it will run until the heat death
of the universe failing to find a smaller covering. Backtracking turned out
to be necessary: the first ("100% greedy") cover it found used 21 6-sets.

The _general_ minimum set-cover problem is NP-hard, so there's no evident
reason to hope that this can be done by any poly-time algorithm. The sets
here have a lot of structure, though, so perhaps there's a way to out-think
this particular case (don't look at me ;-)). OTOH, that the "100% greedy"
cover was not minimal strongly suggests there's not enough exploitable
structure to make this easy.


.