A estrutura de instâncias patológicas para algoritmos simplex

Tanto quanto eu entendo, todos sabem que as regras de pivô determinísticas para algoritmos simplex têm entradas específicas nas quais o algoritmo requer tempo exponencial (ou pelo menos não polinomial) para encontrar o melhor. Vamos chamar essas instâncias de "patológicas", já que geralmente (ou seja, na maioria das entradas) o algoritmo simplex termina rapidamente. Lembro-me do meu curso de programação matemática que os exemplos padrão de instâncias patológicas para regras específicas eram altamente estruturados. Minha pergunta geral é se esse é um artefato de exemplos específicos ou uma característica de instâncias patológicas em geral?

Resultados como análise suavizada e o algoritmo de tempo polinomial que a estende dependem da perturbação da entrada - sugerindo que os exemplos patológicos são muito especiais. Portanto, a intuição de que as instâncias patológicas são altamente estruturadas não parece tão absurda.

Alguém tem alguma ideia específica sobre isso? Ou algumas referências ao trabalho existente? Fui especificamente vago sobre o que quero dizer com 'estruturado' para tentar ser o mais abrangente possível, mas sugestões sobre como definir melhor o 'estruturado' também seriam úteis. Quaisquer conselhos ou referências são muito apreciados!

Amenta e Ziegler provaram que todas as construções atualmente conhecidas de instâncias de tempo exponencial para simplex seguem uma estrutura específica que eles chamam de "produtos deformados":

Produtos deformados e sombras máximas de polítopos de Amenta e Ziegler

No entanto, acho que não há motivo para acreditar que todas as instâncias ruins para simplex tenham essa estrutura. Provavelmente, este é apenas um artefato do processo de pesquisa:

1. Klee e Minty encontraram o primeiro exemplo de tempo exponencial.
2. Outros pesquisadores examinaram as técnicas de Klee e Minty e as estenderam a outras regras de pivô. Eles naturalmente seguiram o caminho de menor resistência e seguiram o cubo de Klee-Minty o mais próximo possível.
3. Quando alguém encontra um mau exemplo para uma regra de pivô, não há incentivo para as pessoas procurarem mais. Como resultado, todos os maus exemplos que conhecemos têm uma estrutura semelhante.