Как определить сложность симплексного времени (т. Е. Максимальный поток)

Question

Симплексный алгоритм имеет экспоненциальную сложность времени в худшем случае. Все же это все еще часто используется на практике. Как определить среднюю сложность по времени для определенной задачи (решаемой с помощью симплекса).

Например, какова средняя временная сложность задачи о максимальном потоке, решаемой с помощью симплексного алгоритма. (Вики имеет временную сложность для всех других алгоритмов)

Спасибо за ваше время.

Answer 1

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

РЕДАКТИРОВАТЬ : Да, вот источники:

Nocedal, J. and Wright, SJ.New York: Springer-Verlag, 1999.

Forsgren, A .;Gill, PE;и Райт М.Х. «Внутренние методы нелинейной оптимизации».SIAM Rev. 44, 525-597, 2002.

Я прочитал это в первой книге, и, очевидно, это было доказано в отдельной статье (Forsgren).Вы можете найти любой из университетской библиотеки.

Answer 2

Если это все еще интересно.Временная сложность симплекса составляет O ((n + m) * n).

n - количество переменных.

m - ограничения неравенства.

Почему?Поскольку число итераций может быть не более n + m в случае n, которое является верхней границей для числа вершин.

Но эта верхняя граница является экспоненциальной по n.