シンプレックスアルゴリズムは、指数的な最悪の場合の時間の複雑さを有すると言われています。しかしそれはまだ実際にはしばしば使われています。特定の問題（シンプレックスで解決される）の平均時間複雑度をどのように決定できますか。シンプレックス時間の複雑さを決定する方法（すなわち、最大流量）
たとえば、シンプレックスアルゴリズムで解決される最大フロー問題の平均時間複雑度はどのくらいですか？ （Wikiは他のすべてのアルゴリズムでは時間の複雑さがあります）
ありがとうございました。
ケースの複雑さの平均は分析するのが難しく、リニアプログラムの分布によって異なります。私はいくつかの一般的な分布の下で多項式時間であることが分かった。私は現在、紙を見つけることができません。
EDIT：
Nocedal、J.およびライト、S. J.数値最適化：はい、ここで供給源です。 New York：Springer-Verlag、1999.
Forsgren、A .; Gill、P.E。 Wright、M.H. "非線形最適化のための内部方法"。 SIAM Rev。44、525-597、2002.
私は最初の本でそれを読んで、明らかにそれは別紙（フォーズグレン）で証明されました。いずれかの大学の図書館で見つけることができます。
まだ興味がある場合。シンプレックスの時間複雑度はO（（n + m）* n）です。
n - 変数の数。
m - 不等式制約。
なぜですか？反復の回数は、頂点の数の上限であるn の場合、n + m以下である可能性があるためです。
しかし、この上限はnで指数関数的です。
音が宿題/テストのようなものです。 –
+1これは実際には本当に深い疑問です。誰かがこれを以前に働かせたかどうかはわかりません。私は答えを聞くのが非常に興味があります。 – templatetypedef