Структура патологических случаев для симплексных алгоритмов

Насколько я понимаю, все известные детерминированные сводные правила для симплексных алгоритмов имеют конкретные входные данные, для которых алгоритму требуется экспоненциальное время (или, по крайней мере, не полиномиальное), чтобы найти оптимальный. Давайте назовем эти случаи «патологическими», поскольку обычно (т. Е. На большинстве входов) симплексный алгоритм быстро завершается. Из курса математического программирования я помню, что стандартные примеры патологических примеров для конкретных правил были очень структурированы. Мой общий вопрос: если это артефакт конкретных примеров или особенность патологических случаев в целом?

Такие результаты, как сглаженный анализ и расширяющий его алгоритм полиномиального времени, полагаются на возмущение входных данных, что предполагает патологические примеры очень особенные. Следовательно, интуиция о том, что патологические случаи высоко структурированы, не кажется слишком надуманной.

У кого-нибудь есть какие-то конкретные идеи по этому поводу? Или некоторые ссылки на существующие работы? Я был совершенно неясен в отношении того, что я имею в виду под «структурированным», пытаясь быть настолько всеобъемлющим, насколько это возможно, но предложения о том, как лучше определить «структурированный», также были бы полезны. Любые советы или рекомендации с благодарностью!

Амента и Циглер доказали, что все известные в настоящее время конструкции экземпляров экспоненциального времени для симплекса следуют определенной структуре, которую они называют «деформированными продуктами»:

Деформированные произведения и максимальные тени многогранников Амента и Циглера

Однако я не думаю, что есть основания полагать, что все плохие случаи для симплекса имеют такую ​​структуру. Вероятно, это просто артефакт исследовательского процесса:

1. Кли и Минти нашли первый экспоненциальный пример времени.
2. Другие исследователи изучили и методы Кли и Минти и расширили их до других основных правил. Естественно, они пошли по пути наименьшего сопротивления и следовали за кубом Кли-Минти как можно ближе.
3. Когда кто-то находит один плохой пример для сводного правила, у людей нет стимула искать больше. В результате все плохие примеры, о которых мы знаем, имеют похожую структуру.