TY - GEN
T1 - Random Walks on the Vertices of Transportation Polytopes with Constant Number of Sources
AU - Cryan, Mary
AU - Dyer, Martin
AU - Müller, Haiko
AU - Stougie, Leen
PY - 2003
Y1 - 2003
N2 - We consider the problem of uniformly sampling a vertex of a transportation polytope with m sources and n destinations, where m is a constant. We analyse a natural random walk on the edge-vertex graph of the polytope. The analysis makes use of the multicommodity flow technique of Sinclair [20] together with ideas developed by Morris and Sinclair [15, 16] for the knapsack problem, and Cryan et al. [2] for contingency tables, to establish that the random walk approaches the uniform distribution in time nO(m2).
AB - We consider the problem of uniformly sampling a vertex of a transportation polytope with m sources and n destinations, where m is a constant. We analyse a natural random walk on the edge-vertex graph of the polytope. The analysis makes use of the multicommodity flow technique of Sinclair [20] together with ideas developed by Morris and Sinclair [15, 16] for the knapsack problem, and Cryan et al. [2] for contingency tables, to establish that the random walk approaches the uniform distribution in time nO(m2).
M3 - Conference contribution
SN - 0-89871-538-5
T3 - SODA '03
SP - 330
EP - 339
BT - Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms
PB - Society for Industrial and Applied Mathematics
CY - Philadelphia, PA, USA
ER -