Talk:SMAWK algorithm

Please do not delete this page. The algorithm is quite notable. The co-authors of the SMAWK algorithm include the notable Peter Shor, Maria Klawe, and Alok Aggarwal. Someone (like me) needs to add more stuff. Vegasprof (talk) 00:56, 29 July 2013 (UTC)

Hey, long time no see. I added some more, enough to make it obvious that it's notable, but it could use more including a description of the algorithm and a better explanation of why totally monotone arrays come up in the applications. There's an implementation at http://www.ics.uci.edu/~eppstein/PADS/SMAWK.py that might be worth including as an external link — I'm not going to add it myself but someone else can. And why does Alok not have an article? —David Eppstein (talk) 02:58, 6 August 2013 (UTC)

Clarifying definition

I think the following definition is very confusing: "For the purposes of this algorithm, a matrix is defined to be monotone if each row's minimum value occurs in a column which is equal to or greater than the column of the previous row's minimum." I would love to be able to improve it, but unfortunately I am myself struggling to understand it; every other definition I find are either worse or I can't see the equivalence... Maybe this one is one of the clearest ones: http://dailyhaskellexercise.tumblr.com/post/57781874558/column-minima-in-a-totally-monotone-matrix 01:29, 27 January 2016 (UTC) Zoltan