Talk:Criss-cross algorithm: Difference between revisions

Revision as of 20:04, 22 March 2011

Revision as of 20:05, 22 March 2011

Line 12:

::That's helpful. At least the phrase "Klee-Minty" should go!

::Caveat: I have not yet provided a reference to the expected behavior of the criss cross algorithm (which is D on cubes of dimension D, I believe). The expected number of steps of the simplex algorithm is also linear under a wide class of models (which are incompatible with reality, alas); the expected running time is usually thought to be about 3D on practical problems.

::I simplified it a bit. I shall try to quickly find a reference to the expected behavior of the algorithms. <small><span style="border:1px solid black;padding:1px;">[[User:Kiefer.Wolfowitz|<font style="color:blue;background:yellow;">&nbsp;'''Kiefer'''.'''Wolfowitz'''&nbsp;</font>]]</span></small>&nbsp;([[User talk:Kiefer.Wolfowitz#top|Discussion]]) 19:59, 22 March 2011 (UTC)

::Maybe this would work better?

** '''Did you know''' ... that the '''[[criss-cross algorithm]]''' and the [[simplex algorithm]] can visit all&nbsp;2^''D'' corners of a <!-- the [[Victor Klee|Klee]]–Minty --> [[unit cube|cube]] in [[dimension (vector space)|dimension]]&nbsp;''D'' but visit only&nbsp;''D'' corners [[expected value|on average]]?

::If you like this, then I canshould find a reference. Best regards, <small><span style="border:1px solid black;padding:1px;">[[User:Kiefer.Wolfowitz|<font style="color:blue;background:yellow;">&nbsp;'''Kiefer'''.'''Wolfowitz'''&nbsp;</font>]]</span></small>&nbsp;([[User talk:Kiefer.Wolfowitz#top|Discussion]]) 20:04, 22 March 2011 (UTC)