Según tengo entendido, todos saben que las reglas de pivote deterministas para algoritmos simplex tienen entradas específicas en las que el algoritmo requiere tiempo exponencial (o al menos no polinomial) para encontrar el óptimo. Llamemos a estas instancias 'patológicas' ya que generalmente (es decir, en la mayoría de las entradas) el algoritmo simplex termina rápidamente. Recuerdo de mi curso de programación matemática que los ejemplos estándar de instancias patológicas para reglas específicas estaban altamente estructurados. Mi pregunta general es si esto es un artefacto de los ejemplos específicos, o una característica de las instancias patológicas en general.
Los resultados como el análisis suavizado y el algoritmo de tiempo polinómico que lo extiende dependen de perturbar la entrada, lo que sugiere que los ejemplos patológicos son muy especiales. Por lo tanto, la intuición de que las instancias patológicas están altamente estructuradas no parece tan descabellada.
¿Alguien tiene alguna idea específica sobre esto? ¿O algunas referencias al trabajo existente? He sido específicamente impreciso sobre lo que quiero decir con 'estructurado' para tratar de ser lo más abarcador posible, pero las sugerencias sobre cómo precisar mejor 'estructurado' también serían útiles. Cualquier consejo o referencia son muy apreciados!
fuente
Respuestas:
Amenta y Ziegler demostraron que todas las construcciones actualmente conocidas de instancias de tiempo exponencial para simplex siguen una estructura particular que llaman "productos deformados":
Sin embargo, no creo que haya ninguna razón para creer que todas las instancias malas para simplex tengan esta estructura. Probablemente esto sea solo un artefacto del proceso de investigación:
fuente