Crate smawk 

This crate implements various functions that help speed up dynamic programming, most importantly the SMAWK algorithm for finding row or column minima in a totally monotone matrix with m rows and n columns in time O(m + n). This is much better than the brute force solution which would take O(mn). When m and n are of the same order, this turns a quadratic function into a linear function.

Examples

Computing the column minima of an m × n Monge matrix can be done efficiently with smawk::column_minima:

use smawk::Matrix;

let matrix = vec![
    vec![3, 2, 4, 5, 6],
    vec![2, 1, 3, 3, 4],
    vec![2, 1, 3, 3, 4],
    vec![3, 2, 4, 3, 4],
    vec![4, 3, 2, 1, 1],
];
let minima = vec![1, 1, 4, 4, 4];
assert_eq!(smawk::column_minima(&matrix), minima);

The minima vector gives the index of the minimum value per column, so minima[0] == 1 since the minimum value in the first column is 2 (row 1). Note that the smallest row index is returned.

Definitions

Some of the functions in this crate only work on matrices that are totally monotone, which we will define below.

Monotone Matrices

We start with a helper definition. Given an m × n matrix M, we say that M is monotone when the minimum value of row i is found to the left of the minimum value in row i' where i < i'.

More formally, if we let rm(i) denote the column index of the left-most minimum value in row i, then we have

rm(0) ≤ rm(1) ≤ ... ≤ rm(m - 1)

This means that as you go down the rows from top to bottom, the row-minima proceed from left to right.

The algorithms in this crate deal with finding such row- and column-minima.

Totally Monotone Matrices

We say that a matrix M is totally monotone when every sub-matrix is monotone. A sub-matrix is formed by the intersection of any two rows i < i' and any two columns j < j'.

This is often expressed as via this equivalent condition:

M[i, j] > M[i, j']  =>  M[i', j] > M[i', j']

for all i < i' and j < j'.

Monge Property for Matrices

A matrix M is said to fulfill the Monge property if

M[i, j] + M[i', j'] ≤ M[i, j'] + M[i', j]

for all i < i' and j < j'. This says that given any rectangle in the matrix, the sum of the top-left and bottom-right corners is less than or equal to the sum of the bottom-left and upper-right corners.

All Monge matrices are totally monotone, so it is enough to establish that the Monge property holds in order to use a matrix with the functions in this crate. If your program is dealing with unknown inputs, it can use monge::is_monge to verify that a matrix is a Monge matrix.

Online Column Minima and Dynamic Programming

In the standard offline SMAWK algorithm, the entire matrix must be known and queryable upfront. However, many dynamic programming problems (like the Least Weight Subsequence problem) involve finding a sequence of indices to minimize a transition cost of the form:

v(0) = initial
v(j) = min { v(i) + w(i, j) | 0 <= i < j }  for j > 0

If the transition weight function w(i, j) satisfies the Monge property, the matrix M[i, j] = v(i) + w(i, j) is totally monotone. However, the matrix entries in column j cannot be computed until the optimal prefix values v(i) for all i < j are finalized. This is an online dependency constraint.

The online_column_minima function solves this online dynamic programming problem in O(n) time. It wraps the core SMAWK algorithm inside an online check-and-correct harness (based on the Galil-Park algorithm), executing matrix queries dynamically as the input prefix calculations are completed.

A prime practical application of this is the Knuth-Plass paragraph line-breaking algorithm (used in TeX and crates like textwrap). By framing word wrapping as a concave least weight subsequence problem, the optimal line breaks of a paragraph of n words can be found in O(n) time instead of O(n²).

References

• Alok Aggarwal, Maria M. Klawe, Shlomo Moran, Peter Shor, and Robert Wilber. Geometric applications of a matrix searching algorithm. Algorithmica, 2(1):195–208, 1987.
• Robert Wilber. The concave least-weight subsequence problem revisited. Journal of Algorithms, 9(3):418–425, 1988.
• Zvi Galil and Kunsoo Park. A linear-time algorithm for concave one-dimensional dynamic programming. Information Processing Letters, 33(6):309–313, 1990.
• Donald E. Knuth and Michael F. Plass. Breaking paragraphs into lines. Software: Practice and Experience, 11(11):1119–1184, 1981.

Modules

monge

Functions for generating and checking Monge arrays.

Traits

Matrix

Minimal matrix trait for two-dimensional arrays.

Functions

column_minima

Compute column minima in O(m + n) time.

online_column_minima

Compute upper-right column minima in O(m + n) time.

row_minima

Compute row minima in O(m + n) time.

smawk_column_minimaDeprecated

smawk_row_minimaDeprecated