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

17

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

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

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

Артем Казнатчеев
источник
1
Я не уверен, что понял ваш вопрос, но противоположность «структурированной» кажется «случайной». Если симплексный алгоритм с определенным правилом поворота уже неэффективен для случайных случаев (с высокой вероятностью, согласно некоторому естественному распределению ), вероятно, люди не заинтересованы в создании плохого примера для этого конкретного правила поворота, потому что это конкретное правило поворота в основном бесполезно.
Цуёси Ито
Вы спрашиваете: для фиксированного правила поворота, какова вероятность того, что случайный случай будет патологическим? т.е. анализ среднего случая алгоритма?
Каве
Я не спрашиваю вероятность того, что случайный случай является патологическим. Я действительно просто спрашиваю, имеют ли патологические случаи особую структуру для них. Как указывает Цуёси, я действительно должен ограничить это «хорошими» правилами для пивотов, что бы это ни значило. Любые предложения о том, как сделать это более ясным?
Артем Казнатчеев
4
Я полагаю, что многие патологические случаи - это кубы, стороны которых были злонамеренно возмущены, но я смотрел на это достаточно давно, чтобы моя память могла быть совершенно неправильной.
Питер Шор

Ответы:

16

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

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

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

  1. Кли и Минти нашли первый экспоненциальный пример времени.
  2. Другие исследователи изучили и методы Кли и Минти и расширили их до других основных правил. Естественно, они пошли по пути наименьшего сопротивления и следовали за кубом Кли-Минти как можно ближе.
  3. Когда кто-то находит один плохой пример для сводного правила, у людей нет стимула искать больше. В результате все плохие примеры, о которых мы знаем, имеют похожую структуру.
Ян
источник
1
Я всегда люблю социологические ответы на математический вопрос;). Спасибо за ответ! Я более подробно рассмотрю AmentaZiegler1996, знаете ли вы о результатах с 96 года, которые хорошо работают на деформированных продуктах? Я нашел статью Нормана Заде (с 1980 по 2009 год), в которой даже в версии 80-х [ stanford.edu/group/SOL/reports/OR-80-27.pdf ] упоминается преодоление деформированной конструкции продукта.
Артем Казнатчеев
«Деформированный продукт» был явно интуитивным понятием в сообществе ЛП за десятилетия до того, как Нина и Гюнтер формализовали его. Конечно, это точное описание кубов Кли-Минти!
Джефф
1
См. Также экспоненциальные нижние оценки Матушека и Сабо для СЛУЧАЙНОГО
КРАЯ