SMAWK Algorithm

The SMAWK algorithm is a method for finding the minimum entry in every row of an implicitly defined matrix that is totally monotone, meaning that as you move down through the rows, the column position of each row's minimum can only move rightward or stay the same. Rather than examining all entries directly, it finds every row minimum in O(c(1 + log(r/c))) time for an r-row, c-column matrix, a substantial improvement for matrices with many more rows than columns, using a prune and search strategy that discards columns which can never hold a row minimum through a stack-based preprocessing step similar to a Graham scan, before recursively solving the reduced problem. The algorithm's name is formed from the initials of its five inventors, Peter Shor, Shlomo Moran, Alok Aggarwal, Robert Wilber and Maria Klawe, who published it in the journal Algorithmica in 1987. This description is adapted from Wikipedia contributors under CC BY-SA 4.0; changes were made. https://creativecommons.org/licenses/by-sa/4.0/