Birkhoff algorithm
Birkhoff's algorithm (also called Birkhoff-von-Neumann algorithm) is an algorithm for decomposing a bistochastic matrix into a convex combination of permutation matrices. It was published by Garrett Birkhoff in 1946. It has many applications. One such application is for the problem of fair random assignment: given a randomized allocation of items, Birkhoff's algorithm can decompose it into a lottery on deterministic allocations.
Wikipedia contributors, "Birkhoff algorithm", Wikipedia, revision 1374703766, retrieved 20 November 2026, source, CC BY-SA 4.0.