¿Cuál es la complejidad computacional de resolver un programa lineal con $ m $ restricciones en $ n $ variables?
Respuestas
¿Demasiados anuncios?
Atticus Zambrana
Puntos
51
Lo mejor posible (en mi opinión) es de Michael Cohen, Yin Tat Lee y Zhao Song: Resolviendo un programa lineal en el tiempo actual de multiplicación de matrices. https://arxiv.org/abs/1810.07896 (STOC 2019) Espero que esto ayude.
Zhao Song
Puntos
26
El resultado de la marca en 2020 desaleatorizó el resultado de Cohen, Lee y Song. Aquí está el enlace https://arxiv.org/pdf/1910.11957.pdf
