Approximate version of a balanced incomplete block diagram

Question

Let $S$ be a set of some size $n$. I'm interested in knowing about combinatorial designs that are approximately balanced incomplete block designs, that I want a collection of subsets $C$ of $S$ such that every pair of elements of $S$ appears in at least one element of $C$, all the elements of $C$ are approximately the same size, and every element appears approximately the same number of times. Obviously there are many trivial examples, but those aren't interesting. Ideally given $n$ there would be a set where $C$ is not "too large" and the elements of $C$ are also not "too large", for some definition of "too large". Most of the literature I've looked at considers weaker exact conditions.

I'm asking this question because I have a massive computation to carry out on multiple machines, and the computation considers a pair of big files at a time. I want to minimize the number of files each of my workers read, while also keeping down the number of workers. Papers, proofs, guidance on what I should be searching for are all welcome: my combinatorial knowledge is shamefully weak.

Answer 1

To expand on my comments above, an analogous problem is covering a graph by cliques. Consider the relation on the set F of files as (a,b) is in the relation if the (distinct) files a and b are to be processed. The result is like a directed graph with F as the set of vertices and the relation determining the edges. Now for p and element of the set P of processing units, you want to associate p to some of the edges. (More generally, you might assign a set or sequence of members from P to an edge to indicate how the pair of files to process.)

The setup above is general and perhaps more complex than it needs to be, but should give you ideas on how to write the code so that you can generalize when the customer asks for it. Let's simplify the picture by making the graph undirected, assigning only one processor to each edge (so a simple coloring of edges rather than a list coloring), and let's pretend that cliques are important (small subsets G of F and all edges between any two points are present ) for some reason, say optimizing disk access means a processor should stick to two disks, and G may represent a subset of the files on those two disks.

We now have a situation where we want to cover, possibly with overlap, all the edges of F (which we assume has all possible edges) by smaller cliques, perhaps of the same size. Enter the La Jolla Covering Repository: a collection of covering designs where a list of subsets of size k from a set of size v are listed so that every set of size t (for this problem, t=2), is covered or a subset of one of the sets of size k. One can divide this list among several processors to ensure all processorsto assign the tasks to be done on all pairs of files.

Since I don't like repetition, I would maintain a structure shared by all processors or used by a master to assign to a worker which would list all pairs of files and the information of which pair is being (or going to be) processed by which processor. Of course, I might change my mind depending on resource availability and problem size.

Gerhard "Or To Make Me Happy" Paseman, 2012.07.15

Answer 2

One related structure is an incidence geometry. Each pair of points determine a unique line. Every $2$-design with $\lambda = 1$ is an example of an incidence geometry, but incidence geometries are more flexible.

Given an incidence geometry on $V$, you can induce an incidence geometry on $W \subset V$ by taking the lines to be the intersections of lines with $W$ (except you throw out the intersections of size at most $1$). For example, there are Steiner triple systems (block designs where the blocks have size $3$ and $\lambda=1$) if and only if the number of vertices is $1$ or $3$ mod $6$. There is no Steiner triple system on $11$ vertices, but you can take a Steiner triple system on $13$ vertices with $26$ blocks/lines and delete $2$ points (and the line through them which only contains $1$ point now) to get an incidence geometry on $11$ points with $25$ lines so that each line contains $2$ or $3$ points.

This might not work well over all sets of parameters. Block designs with more than $1$ block have more blocks than points (Fisher's inequality). The same is true for incidence geometries (de Bruijn–Erdős). Projective planes are examples of equality. If you have fewer workers than files, so that workers have to handle more than about the square root of the number of files, then you aren't looking for a small deviation from a block design.