Content deleted Content added
m →Did You Know?: link cube |
→Did You Know?: that the '''criss-cross algorithm''' and the simplex algorithm can visit all 2<sup>''D''</sup> corners of a <!-- the Klee–Minty --> cube in dimension ' |
||
Line 6:
[[Template_talk:Did_you_know#Criss-cross_algorithm|I nominated the following hook]]: <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]]) 00:57, 22 March 2011 (UTC)
* '''Did you know'' ... that the '''[[criss-cross algorithm]]''' and the [[simplex algorithm]] are not [[time complexity|polynomial-time algorithm]]s <!-- for [[linear programming|linear optimization]] --> because they visit all 2<sup>''D''</sup> corners of a <!-- the [[Victor Klee|Klee]]–Minty --> [[unit cube|cube]] in [[dimension (vector space)|dimension]] ''D''?
: That sounds a bit difficult for a DYK, don't you think? I mean, is there any way it could be worded to be more accessible? [[User:CRGreathouse|CRGreathouse]]<small> ([[User talk:CRGreathouse|t]] | [[Special:Contributions/CRGreathouse|c]])</small> 04:25, 22 March 2011 (UTC)
Line 13:
::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;"> '''Kiefer'''.'''Wolfowitz''' </font>]]</span></small> ([[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 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 can 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)
| |||