2 removed xtra word

The set of $n\times n$ real, nonnegative matrices whose rows and columns sum to one forms the well-known Birkhoff polytope

Recently someone asked me if I knew

How to sample (naturally in polynomial time), time) uniformly at random, from the Birkhoff polytope?

Clearly, modulo a few hacks, I did not have a good answer, so am repeating the above question here (the hacks included trying to exploit that every doubly stochastic matrix is a convex combination of permutation matrices).

1

Sampling from the Birkhoff polytope

The set of $n\times n$ real, nonnegative matrices whose rows and columns sum to one forms the well-known Birkhoff polytope

Recently someone asked me if I knew

How to sample (naturally in polynomial time), uniformly at random, from the Birkhoff polytope?

Clearly, modulo a few hacks, I did not have a good answer, so am repeating the above question here (the hacks included trying to exploit that every doubly stochastic matrix is a convex combination of permutation matrices).