Sampling from the Birkhoff polytope

This is, to my knowledge, still open. It is connected to the problem of computing the volume of the Birkhoff polytope (or computing the volume of its faces), which is known in closed form only for $n\le 14$. This is also equivalent toThis could be approached by counting non-negative integer matrices with equal row and column sums (because you can read the volume from the leading coefficient of the Ehrhart polynomial, like it is done in the paper The Ehrhart polynomial of the Birkhoff polytope, by Matthias Beck and Dennis Pixton. There are algorithms that sample from distributions that are close to uniform (see the articles below).

The problem is quite old, but there has been a revival of interest recently by several authors. I can point you to a few

• "What does a random contingency table look like?", by A. Barvinok
• "On random, doubly stochastic, tri-diagonal matrices", by P. Diaconis and P. Matchett Wood
• "Properties of Uniform Doubly Stochastic Matrices" by S. Chatterjee, P. Diaconis, A. Sly
• Gibbs/Metropolis algorithms on a convex polytope by P. Diaconis, G. Lebeau, L. Michel

There is a polynomial time algorithm based on random walks to approximately sample from any $n$-dimensional convex body which also applies to the Birkhoff polytope. This is an algorithm by Dyer, Frieze, and Kannan: A random polynomial time algorithm for approximating the volume of convex bodies. Quite a few improvements were found. See e.g. , Blocking Conductance and Mixing in Random Walks, R. Kannan, L. Lovasz and R. Montenegro, in Combinatorics, Probability and Computing (2005)