Live briefing
Everything about Birkhoff algorithm
Tool for working with matrices
Birkhoff's 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 →
🧠Start here: a 6-step reading path
- Read the overview: Birkhoff algorithmA 5-minute orientation
- Read the landmark paper: Notes on the Birkhoff Algorithm for Doubly Stochastic MatricesCited 35 times
- Go sideways: Doubly stochastic matrixA closely related topic
- Go sideways: Birkhoff polytopeA closely related topic
đź“– Definitions
No dictionary entry for this exact phrase.
🗂️ The subject at a glance
🏆 Landmark papers (most cited)
Notes on the Birkhoff Algorithm for Doubly Stochastic Matrices
On an Algorithm of G. Birkhoff Concerning Doubly Stochastic Matrices
Enhanced Birkhoff–von Neumann decomposition algorithm for input queued switches
A fast algorithm for the multivariate Birkhoff interpolation problem
A new algorithm for Birkhoff normalization of Hamiltonian systems
RHBPIA: a new algorithm for computing Hermite-Birkhoff interpolation polynomials
RHBMPIA: a new algorithm for computing Hermite-Birkhoff matrix interpolation polynomials
An algorithm for Hermite-Birkhoff interpolation
đź“š Books worth reading
Open Library didn't respond; try again in a moment.
đź”— Related topics
- Doubly stochastic matrix In mathematics, especially in probability and combinatorics, a doubly stochastic matrix (also called bistochastic matrix) is a square matrix X = ( x i…
- Birkhoff polytope The Birkhoff polytope B n {\displaystyle B_{n}} is the convex polytope in R n 2 {\displaystyle \mathbb {R} ^{n^{2}}} whose points are the doubly stochastic…
- List of named matrices This article lists some important classes of matrices used in mathematics, science and engineering. A matrix (plural matrices, or less commonly matrixes)…
- Perron–Frobenius theorem In matrix theory, the Perron–Frobenius theorem, proved in its first part by Oskar Perron (1907) and extended by Georg Frobenius (1912), asserts that a…
- Permutation matrix In mathematics, particularly in matrix theory, a permutation matrix is a square binary matrix that has exactly one entry of 1 in each row and each column…
- Pfaffian In mathematics, the determinant of an m-by-m skew-symmetric matrix can always be written as the square of a polynomial in the matrix entries, a polynomial…
- Hafnian In mathematics, the hafnian is a scalar function of a symmetric matrix that generalizes the permanent. The hafnian was named by Eduardo R. Caianiello "to…
- Unistochastic matrix In mathematics, a unistochastic matrix (also called unitary-stochastic) is a doubly stochastic matrix whose entries are the squares of the absolute values…