Find the smallest set group to cover all combinatory possibilities

Question

I'm making some exercises on combinatorics algorithm and trying to figure out how to solve the question below:

Given a group of 25 bits, set (choose) 15 (non-permutable and order NON matters):

n!/(k!(n-k)!) = 3.268.760

Now for every of these possibilities construct a matrix where I cross every unique 25bit member against all other 25bit member where in the relation in between it there must be at least 11 common setted bits (only ones, not zeroes).

Let me try to illustrate representing it as binary data, so the first member would be:

0000000000111111111111111 (10 zeros and 15 ones) or (15 bits set on 25 bits)
0000000001011111111111111 second member
0000000001101111111111111 third member
0000000001110111111111111 and so on....
...
1111111111111110000000000 up to here. The 3.268.760 member.

Now crossing these values over a matrix for the 1 x 1 I must have 15 bits common. Since the result is >= 11 it is a "useful" result.

For the 1 x 2 we have 14 bits common so also a valid result.

Doing that for all members, finally, crossing 1 x 3.268.760 should result in 5 bits common so since it's < 11 its not "useful".

What I need is to find out (by math or algorithm) wich is the minimum number of members needed to cover all possibilities having 11 bits common.

In other words a group of N members that if tested against all others may have at least 11 bits common over the whole 3.268.760 x 3.268.760 universe.

Using a brute force algorithm I found out that with 81 25bit member is possible achive this. But i'm guessing that this number should be smaller (something near 12).

I was trying to use a brute force algorithm to make all possible variations of 12 members over the 3.268.760 but the number of possibilities it's so huge that it would take more than a hundred years to compute (3,156x10e69 combinations).

I've googled about combinatorics but there are so many fields that i don't know in wich these problem should fit.

So any directions on wich field of combinatorics, or any algorithm for these issue is greatly appreciate.

PS: Just for reference. The "likeness" of two members is calculated using:

(Not(a xor b)) and a

After that there's a small recursive loop to count the bits given the number of common bits.

EDIT: As promissed (@btilly)on the comment below here's the 'fractal' image of the relations or link to image

The color scale ranges from red (15bits match) to green (11bits match) to black for values smaller than 10bits.

This image is just sample of the 4096 first groups.

Answer 1

tl;dr: you want to solve dominating set on a large, extremely symmetric graph. btilly is right that you should not expect an exact answer. If this were my problem, I would try local search starting with the greedy solution. Pick one set and try to get rid of it by changing the others. This requires data structures to keep track of which sets are covered exactly once.

EDIT: Okay, here's a better idea for a lower bound. For every k from 1 to the value of the optimal solution, there's a lower bound of [25 choose 15] * k / [maximum joint coverage of k sets]. Your bound of 12 (actually 10 by my reckoning, since you forgot some neighbors) corresponds to k = 1. Proof sketch: fix an arbitrary solution with m sets and consider the most coverage that can be obtained by k of the m. Build a fractional solution where all symmetries of the chosen k are averaged together and scaled so that each element is covered once. The cost of this solution is [25 choose 15] * k / [maximum joint coverage of those k sets], which is at least as large as the lower bound we're shooting for. It's still at least as small, however, as the original m-set solution, as the marginal returns of each set are decreasing.

Computing maximum coverage is in general hard, but there's a factor (e/(e-1))-approximation (≈ 1.58) algorithm: greedy, which it sounds as though you could implement quickly (note: you need to choose the set that covers the most uncovered other sets each time). By multiplying the greedy solution by e/(e-1), we obtain an upper bound on the maximum coverage of k elements, which suffices to power the lower bound described in the previous paragraph.

Warning: if this upper bound is larger than [25 choose 15], then k is too large!