Un grupo de investigadores, encabezado por Sepehr Assadi, ha demostrado que ningún algoritmo de semi-streaming en una sola pasada —determinista o aleatorio— puede aproximar el problema del emparejamiento máximo por encima de la mitad. El resultado, publicado en arXiv el 20 de julio de 2026, cierra una pregunta abierta en el área del procesamiento de grafos en streaming que llevaba más de dos décadas sin resolverse, desde la introducción del modelo. La consecuencia práctica es directa: el sencillo algoritmo voraz (greedy) ya era óptimo, sin necesidad de procedimientos más sofisticados.
La demostración se apoya en el llamado "blueprint framework", una técnica introducida previamente por los mismos autores para traducir la obtención de cotas inferiores en problemas de emparejamiento semi-streaming a la construcción de ciertos objetos combinatorios denominados blueprints. En el artículo, los investigadores presentan una construcción óptima de estos blueprints que, al integrarse en el marco, produce la cota inferior anunciada.
El trabajo también resuelve una cuestión pendiente sobre el emparejamiento online con preemption: la mejor razón competitiva posible es 1/2, de nuevo idéntica a la del algoritmo voraz ingenuo. La investigación combina teoría de grafos, complejidad de streaming y técnicas de reducción, y sitúa el rendimiento del método voraz como techo del modelo, no como punto de partida a mejorar.