Dos investigadores han mejorado un famoso límite matemático sobre cómo repartir objetos de forma equilibrada.
Repartir objetos en dos grupos equilibrados se vuelve difícil cuando intervienen muchas variables. La teoría de la discrepancia da forma matemática a esa dificultad: representa cada objeto como un vector y pregunta si es posible asignarlo a un lado u otro de manera que la suma final quede cerca de cero en todas las dimensiones relevantes.
A comienzos de los años ochenta, János Komlós formuló una conjetura audaz. Sostenía que, para vectores de longitud uno, siempre debía existir una división cuya discrepancia quedara por debajo de una constante universal. La afirmación resultaba sorprendente porque esa constante no dependería ni del número de vectores ni del número de dimensiones.
Los avances previos habían reducido el desequilibrio máximo garantizado, pero no habían eliminado su dependencia del tamaño. Desde 1998, el mejor límite conocido era proporcional a la raíz cuadrada del logaritmo de N. Aquella barrera se había convertido en una referencia difícil de mover.
Nikhil Bansal y Haotian Jiang han cambiado esa situación con un algoritmo que controla mejor la asignación. Como en trabajos anteriores, el método empieza repartiendo fracciones de los vectores y las empuja poco a poco hacia decisiones completas. Su diferencia clave es una medida de dependencia: no solo vigila cuánto desequilibrio se acumula, sino cómo un cambio en una característica puede propagarse a las demás.
El resultado garantiza una discrepancia acotada por la cuarta raíz del logaritmo de N, una función de crecimiento muy lento. No demuestra la conjetura de Komlós, pero la vuelve más plausible y ofrece una herramienta eficiente para problemas de optimización, física, finanzas y aprendizaje automático.
Basado en: Max G. Levy, Quanta Magazine