Асимптотическая оценка среднего числа шагов параметрического симплекс-метода

Доказывается анонсированная в [1] оценка среднего числа шагов параметрического варианта симплекс-метода для решения задач линейного программирования относительно некоторого естественного класса статистик на пространстве задач. Если число переменных в задаче равно $n$, а число ограничений типа равенства равно $k$, то для среднего числа шагов $s(n,k)$ справедлива оценка
$$ s(n,k)\le\frac{(k+1)^{1/2}}{2}(\pi\ln n)^{k/2}+O((\ln n)^{(k-1)/2}),\quad n\to\infty. $$
Описывается важный сам по себе грассманов подход к подобным проблемам.