Versión aproximada de un diagrama de bloques incompleto y equilibrado

Question

Dejemos que $S$ sea un conjunto de cierto tamaño $n$ . Estoy interesado en conocer los diseños combinatorios que son diseños de bloques incompletos aproximadamente equilibrados, que quiero una colección de subconjuntos $C$ de $S$ tal que cada par de elementos de $S$ aparece en al menos un elemento de $C$ todos los elementos de $C$ son aproximadamente del mismo tamaño, y cada elemento aparece aproximadamente el mismo número de veces. Obviamente, hay muchos ejemplos triviales, pero esos no son interesantes. Idealmente, dado $n$ habría un conjunto en el que $C$ no es "demasiado grande" y los elementos de $C$ tampoco son "demasiado grandes", por alguna definición de "demasiado grandes". La mayor parte de la literatura que he mirado considera condiciones exactas más débiles.

Hago esta pregunta porque tengo que realizar un cálculo masivo en varias máquinas, y el cálculo considera un par de archivos grandes a la vez. Quiero minimizar el número de archivos que lee cada uno de mis trabajadores, a la vez que mantener bajo el número de trabajadores. Documentos, pruebas, orientación sobre lo que debería buscar son bienvenidos: mis conocimientos de combinatoria son vergonzosamente débiles.

Answer 1

Una estructura relacionada es un geometría de incidencia . Cada par de puntos determina una línea única. Cada $2$ -diseño con $\lambda = 1$ es un ejemplo de geometría de incidencia, pero las geometrías de incidencia son más flexibles.

Dada una geometría de incidencia en $V$ se puede inducir una geometría de incidencia en $W \subset V$ tomando las líneas como las intersecciones de las líneas con $W$ (excepto que se descartan las intersecciones de tamaño como máximo $1$ ). Por ejemplo, hay sistemas triples de Steiner (diseños de bloques en los que los bloques tienen tamaño $3$ y $\lambda=1$ ) si y sólo si el número de vértices es $1$ o $3$ mod $6$ . No hay ningún sistema triple de Steiner en $11$ vértices, pero se puede tomar un sistema triple de Steiner en $13$ vértices con $26$ bloques/líneas y eliminar $2$ puntos (y la línea que los atraviesa que sólo contiene $1$ punto ahora) para obtener una geometría de incidencia en $11$ puntos con $25$ para que cada línea contenga $2$ o $3$ puntos.

Esto podría no funcionar bien en todos los conjuntos de parámetros. Los diseños de bloques con más de $1$ tienen más bloques que puntos ( La desigualdad de Fisher ). Lo mismo ocurre con las geometrías de incidencia (de Bruijn-Erdős). Los planos proyectivos son ejemplos de igualdad. Si tienes menos trabajadores que expedientes, de manera que los trabajadores tienen que manejar más que la raíz cuadrada del número de expedientes, entonces no estás buscando una pequeña desviación de un diseño en bloque.

Answer 2

Para ampliar mis comentarios anteriores, un problema análogo es el de cubrir un gráfico con camarillas. Considere la relación sobre el conjunto F de archivos como (a,b) está en la relación si los archivos (distintos) a y b deben ser procesados. El resultado es como un grafo dirigido con F como conjunto de vértices y la relación determinando las aristas. Ahora, para p y elemento del conjunto P de unidades de procesamiento, se quiere asociar p a alguna de las aristas. (De forma más general, se podría asignar un conjunto o secuencia de miembros de P a una arista para indicar cómo el par de archivos a procesar).

La configuración anterior es general y quizás más compleja de lo necesario, pero debería darle ideas sobre cómo escribir el código para poder generalizar cuando el cliente lo pida. Simplifiquemos el cuadro haciendo que el gráfico sea no dirigido, asignando sólo un procesador a cada arista (así que una simple coloración de aristas en lugar de una coloración de lista), y pretendamos que las camarillas son importantes (pequeños subconjuntos G de F y todas las aristas entre dos puntos cualesquiera están presentes) por alguna razón, digamos que la optimización del acceso al disco significa que un procesador debe ceñirse a dos discos, y G puede representar un subconjunto de los archivos en esos dos discos.

Ahora tenemos una situación en la que queremos cubrir, posiblemente con solapamiento, todas las aristas de F (que suponemos que tiene todas las aristas posibles) por camarillas más pequeñas, quizás del mismo tamaño. Entre en el Repositorio de Cobertura de La Jolla: una colección de diseños de cobertura donde una lista de subconjuntos de tamaño k de un conjunto de tamaño v se enumeran de manera que cada conjunto de tamaño t (para este problema, t=2), está cubierto o un subconjunto de uno de los conjuntos de tamaño k. Uno puede dividir esta lista entre varios procesadores para asegurar que todos los procesadores asignen las tareas a realizar en todos los pares de archivos.

Como no me gusta la repetición, mantendría una estructura compartida por todos los procesadores o utilizada por un maestro para asignar a un trabajador que enumeraría todos los pares de archivos y la información de qué par está siendo (o va a ser) procesado por qué procesador. Por supuesto, podría cambiar de opinión dependiendo de la disponibilidad de recursos y del tamaño del problema.

Gerhard "O para hacerme feliz" Paseman, 2012.07.15