Random walks on the vertices of transportation polytopes with constant number of sources

Mary Cryan, Martin Dyer, Haiko Müller, Leen Stougie

Research output: Contribution to journalArticlepeer-review

Abstract

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 analyze a natural random walk on the edge-vertex graph of the polytope. The analysis makes use of the multicommodity flow technique of Sinclair [Combin Probab Comput 1 (1992), 351--370] together with ideas developed by Morris and Sinclair [SIAM J Comput 34 (2004), 195--226] for the knapsack problem, and Cryan et al. [SIAM J Comput 36 (2006), 247--278] for contingency tables, to establish that the random walk approaches the uniform distribution in time nO(m2).

Original languageEnglish
Pages (from-to)333-355
Number of pages23
JournalRandom Structures and Algorithms
Volume33
Issue number3
DOIs
Publication statusPublished - Oct 2008

Keywords

  • transportation polytope
  • random walk
  • rapid mixing

Fingerprint

Dive into the research topics of 'Random walks on the vertices of transportation polytopes with constant number of sources'. Together they form a unique fingerprint.

Cite this