Demostrado: el algoritmo greedy es óptimo para matching en streaming de una sola pasada

Greedy is optimal for single-pass semi-streaming matching

Un nuevo artículo de Sepehr Assadi, Max Jiang y Mars Xiang demuestra que ningún algoritmo semi-streaming de una sola pasada, ni determinista ni aleatorizado, puede superar una aproximación de 1/2 al problema del matching máximo. Esto confirma la optimalidad del algoritmo greedy y resuelve una pregunta abierta planteada hace más de dos décadas. Los autores extienden el resultado al matching online con preemption, donde la razón competitiva óptima también es 1/2.