Content deleted Content added
→Did You Know?: ce |
→Did You Know?: added some preliminary referencing. The expected behavior of the simplex method (on problems from the unit sphere) is O(D) by Borgwardt and Smale. I don't have Klee & Minty's paper handy, but it seems trivial that a cube drawn fro |
||
Line 16:
** '''Did you know''' ... that the '''[[criss-cross algorithm]]''' and the [[simplex algorithm]] can visit all 2<sup>''D''</sup> corners of a <!-- the [[Victor Klee|Klee]]–Minty --> [[unit cube|cube]] in [[dimension (vector space)|dimension]] ''D'' but visit only ''D'' corners [[expected value|on average]]?
::If you like this, then I should find a reference. Best regards, <small><span style="border:1px solid black;padding:1px;">[[User:Kiefer.Wolfowitz|<font style="color:blue;background:yellow;"> '''Kiefer'''.'''Wolfowitz''' </font>]]</span></small> ([[User talk:Kiefer.Wolfowitz#top|Discussion]]) 20:04, 22 March 2011 (UTC)
::I added some preliminary referencing about average behavior. The expected behavior of the simplex method (on problems from the unit sphere) is O(D) by Borgwardt and Smale. I don't have Klee & Minty's paper handy, but it seems trivial that a cube drawn from the sphere should have D steps on average. (I don't have time to reference properly today: Iterating the bibliography operator initialized with Fukuda & Terlaky should suffice. Sincerely, <small><span style="border:1px solid black;padding:1px;">[[User:Kiefer.Wolfowitz|<font style="color:blue;background:yellow;"> '''Kiefer'''.'''Wolfowitz''' </font>]]</span></small> ([[User talk:Kiefer.Wolfowitz#top|Discussion]]) 20:25, 22 March 2011 (UTC)
| |||