Motivación para desarrollar algoritmos de ruta simple más cortos

8

Estoy leyendo Algoritmos simples de camino más corto eficientes por Donald Goldfarb, Jianxiu Hao y Shen-Roan Kai, quienes consideraron "la especialización del algoritmo simplex primario para el problema de encontrar un árbol de caminos más cortos dirigidos desde un nodo dado a todos los demás nodos en una red de n nodos o encontrar un ciclo dirigido de longitud negativa. Se analizan dos variantes eficientes de este algoritmo simplex de ruta más corta y se demuestra que requieren como máximo pivotes y tiempo ".O ( n 3 )(norte-1)(norte-2)/ /2O(norte3)

Estoy tratando de encontrar la motivación para este artículo y me pregunto si el algoritmo de Bellman-Ford no es lo suficientemente bueno. Funciona en tiempo O(nortemetro) y es bueno para el tipo de gráfico que trata el problema del algoritmo anterior.

Jozef
fuente

Respuestas:

16

Un gran problema abierto en la programación matemática es diseñar un algoritmo de programación lineal de tiempo fuertemente polinómico. Un problema relacionado es si alguna variante del algoritmo simplex se ejecuta en un tiempo fuertemente polinómico. Tiene sentido demostrar primero límites de tiempo polinomiales fuertes para variantes de símplex aplicadas a problemas para los cuales ya sabemos que existen algoritmos de tiempo polinomiales fuertes.

Sasho Nikolov
fuente