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.



Approximate version of a balanced incomplete block diagram
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


