Dos investigadores han mejorado un famoso límite matemático sobre cómo repartir objetos de forma equilibrada.
La teoría de la discrepancia estudia hasta qué punto se pueden repartir objetos entre dos grupos sin crear grandes diferencias. La imagen es sencilla: formar dos equipos de preguntas con habilidades parecidas. El mismo marco sirve para coches, datos o participantes de un estudio clínico, siempre que cada objeto tenga varias características que conviene equilibrar.
La conjetura de Komlós, planteada a comienzos de los años ochenta, afirma algo más fuerte de lo que sugiere la intuición. Si cada objeto se representa como un vector de longitud uno, debería existir siempre una división en dos grupos cuya discrepancia no supere una constante universal. Ese límite no crecería aunque aumentaran el número de objetos o de dimensiones.
Durante décadas, los mejores resultados siguieron dependiendo del tamaño del problema. En 1998 se alcanzó una cota basada en la raíz cuadrada del logaritmo de N, donde N es el número de vectores. Fue un progreso importante, pero todavía quedaba lejos de una constante.
Nikhil Bansal y Haotian Jiang han mejorado esa frontera con un enfoque algorítmico. Su método divide primero los vectores en partes y después los mueve de forma controlada hasta asignarlos por completo a un lado u otro. La novedad está en medir la dependencia entre características: si se altera una, el algoritmo estima cuánto puede cambiar el desequilibrio en las demás.
Con esta idea han logrado una cota de log(N) elevado a un cuarto, una función que crece muy despacio incluso cuando N es grande. El problema sigue abierto, pero el avance refuerza la posibilidad de que la conjetura sea cierta y abre caminos en optimización, física, finanzas y aprendizaje automático.
Basado en: Max G. Levy, Quanta Magazine