Talk:Criss-cross algorithm: Difference between revisions

Revision as of 03:37, 22 March 2011

Latest revision as of 06:38, 13 February 2024

(23 intermediate revisions by 6 users not shown)

Line 1:

{{WikiProject banner shell|class=C|1=

{{maths rating|field=discrete|class=start|importance=mid<!-- low -->}}

{{WikiProject Computer Science|field=algorithm|class=startMathematics|importance=mid<!-- low -->}}

{{WikiProject Systems|field=OperationsComputer research|class=startscience|importance=mid<!-- low -->}}

{{WikiProject Systems|field=Operations research|importance=low}}

}}

{{dyktalk|5 April|2011|entry=... that, while the '''[[criss-cross algorithm]]''' visits all eight corners of the '''[[Klee–Minty cube]]''' when started at a [[worst-case complexity|''worst'' corner]], it visits only three more corners [[expected value|on average]] when started at a [[average-case complexity|''random'' corner]]?}}

==[[Template_talk:Did_you_know#Criss-cross_algorithm|Did You Know?]]==

[[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;">&nbsp;'''Kiefer'''.'''Wolfowitz'''&nbsp;</font>]]</span></small>&nbsp;([[User talk:Kiefer.Wolfowitz#top|Discussion]]) 00:57, 22 March 2011 (UTC)

==[[Template_talk:Did_you_know#Criss-cross_algorithm,_Klee–Minty cube|Did You Know?]]==

* 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&nbsp;2^''D'' corners of the [[Victor Klee|Klee]]–Minty cube in [[dimension (vector space)|dimension]]&nbsp;''D''?

===Old nomination: Inaccessible===

{{hidden begin}}

[[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|<fontspan style="color:blue;background:yellow;">&nbsp;'''Kiefer'''.'''Wolfowitz'''&nbsp;</fontspan>]]</span></small>&nbsp;([[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&nbsp;2^''D'' corners of a <!-- the [[Victor Klee|Klee]]–Minty --> [[unit cube|cube]] in [[dimension (vector space)|dimension]]&nbsp;''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)

: In particular, I don't think many readers—even mathematically sophisticated ones—will know of the Klee–Minty cube, nor the significance of a vector space's dimension. If I were writing it (and I'm not!) I might say something about the fact that it's an exponential-time algorithm that performs far better in practice. Surely there are other things that educated but nonspecialist readers could appreciate? [[User:CRGreathouse|CRGreathouse]]<small> ([[User talk:CRGreathouse|t]] | [[Special:Contributions/CRGreathouse|c]])</small> 19:50, 22 March 2011 (UTC)

::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. <small><span style="border:1px solid black;padding:1px;">[[User:Kiefer.Wolfowitz|<span style="color:blue;background:yellow;">&nbsp;'''Kiefer'''.'''Wolfowitz'''&nbsp;</span>]]</span></small>&nbsp;([[User talk:Kiefer.Wolfowitz#top|Discussion]]) 19:59, 22 March 2011 (UTC)

{{hidden end}}

===[[Template_talk:Did_you_know#Criss-cross_algorithm,_Klee–Minty cube|New hook: Accessible]]===

::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 should find a reference. Best regards, <small><span style="border:1px solid black;padding:1px;">[[User:Kiefer.Wolfowitz|<span style="color:blue;background:yellow;">&nbsp;'''Kiefer'''.'''Wolfowitz'''&nbsp;</span>]]</span></small>&nbsp;([[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|<span style="color:blue;background:yellow;">&nbsp;'''Kiefer'''.'''Wolfowitz'''&nbsp;</span>]]</span></small>&nbsp;([[User talk:Kiefer.Wolfowitz#top|Discussion]]) 20:25, 22 March 2011 (UTC)

:::I nominated the alternative. Thanks for the suggestions. <small><span style="border:1px solid black;padding:1px;">[[User:Kiefer.Wolfowitz|<span style="color:blue;background:yellow;">&nbsp;'''Kiefer'''.'''Wolfowitz'''&nbsp;</span>]]</span></small>&nbsp;([[User talk:Kiefer.Wolfowitz#top|Discussion]]) 21:06, 22 March 2011 (UTC)

:::: Looks good to me. [[User:CRGreathouse|CRGreathouse]]<small> ([[User talk:CRGreathouse|t]] | [[Special:Contributions/CRGreathouse|c]])</small> 23:25, 22 March 2011 (UTC)

:::::I submitted it, along with a graphic. Please consider vetting it at DYK. Thanks again for your feedback. (I evaluated the D and 2^D expressions with D=3, computing 3 and 8 respectively: I trust this does not violate Original Research policy!) Cheers, <small><span style="border:1px solid black;padding:1px;">[[User:Kiefer.Wolfowitz|<span style="color:blue;background:yellow;">&nbsp;'''Kiefer'''.'''Wolfowitz'''&nbsp;</span>]]</span></small>&nbsp;([[User talk:Kiefer.Wolfowitz#top|Discussion]]) 00:40, 23 March 2011 (UTC)

DYK: The article was viewed 4536 times in 201104. <small><span style="border:1px solid black;padding:1px;">[[User:Kiefer.Wolfowitz|<span style="color:blue;background:yellow;">&nbsp;'''Kiefer'''.'''Wolfowitz'''&nbsp;</span>]]</span></small>&nbsp;([[User talk:Kiefer.Wolfowitz#top|Discussion]]) 00:29, 6 April 2011 (UTC)

== Example or Illustration needed ==

The article needs an example, preferably with an illustration, to move up to "B class". <small><span style="border:1px solid black;padding:1px;">[[User:Kiefer.Wolfowitz|<span style="color:blue;background:yellow;">&nbsp;'''Kiefer'''</span>]].[[User talk:Kiefer.Wolfowitz#top|Wolfowitz]]</span></small> 22:35, 30 August 2011 (UTC)