Struktura instancji patologicznych dla algorytmów simpleks

O ile rozumiem, wszyscy znają deterministyczne reguły przestawne dla algorytmów simpleksowych mają określone dane wejściowe, na których algorytm wymaga czasu wykładniczego (lub przynajmniej nie wielomianowego), aby znaleźć optymalne. Nazwijmy te przypadki „patologicznymi”, ponieważ zwykle (tj. Na większości danych wejściowych) algorytm simpleks kończy się szybko. Pamiętam z mojego kursu programowania matematycznego, że standardowe przykłady patologicznych przypadków dla określonych reguł były wysoce ustrukturyzowane. Moje ogólne pytanie brzmi: czy jest to artefakt konkretnych przykładów, czy cecha patologicznych przypadków w ogóle?

Wyniki, takie jak wygładzona analiza i rozszerzający ją algorytm wielomianu czasu , zależą od zakłócenia danych wejściowych - co sugeruje, że przykłady patologiczne są bardzo szczególne. Stąd intuicja, że ​​patologiczne przypadki są wysoce ustrukturyzowane, nie wydaje się tak daleko idąca.

Czy ktoś ma jakieś szczegółowe spostrzeżenia na ten temat? A może jakieś odniesienia do istniejącej pracy? Byłem szczególnie niejasny co do tego, co rozumiem przez „ustrukturyzowany”, aby starać się być tak obejmujący, jak to możliwe, ale przydatne byłyby również sugestie, jak lepiej określić „ustrukturyzowany”. Wszelkie porady i referencje są mile widziane!

Amenta i Ziegler udowodnili, że wszystkie obecnie znane konstrukcje instancji czasu wykładniczego dla simpleksów mają szczególną strukturę, którą nazywają „produktami zdeformowanymi”:

Zdeformowane produkty i maksymalne cienie polytopów autorstwa Amenty i Zieglera

Nie sądzę jednak, aby istniał jakiś powód, by sądzić, że wszystkie złe instancje dla simpleks mają tę strukturę. To prawdopodobnie tylko artefakt procesu badawczego:

1. Klee i Minty znaleźli pierwszy przykład czasu wykładniczego.
2. Inni badacze przyglądali się technikom Klee i Minty i rozszerzyli je na inne zasady obrotu. Naturalnie wybrali ścieżkę najmniejszego oporu i podążyli za kostką Klee-Minty jak najbliżej.
3. Gdy ktoś znajdzie jeden zły przykład reguły przestawnej, nie ma motywacji, by szukać więcej. W rezultacie wszystkie złe przykłady, które znamy, mają podobną strukturę.