Premium
Random walks on the vertices of transportation polytopes with constant number of sources
Author(s) -
Cryan Mary,
Dyer Martin,
Müller Haiko,
Stougie Leen
Publication year - 2008
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20222
Subject(s) - polytope , combinatorics , knapsack problem , mathematics , contingency table , vertex (graph theory) , random walk , constant (computer programming) , discrete mathematics , graph , mathematical optimization , computer science , statistics , programming language
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 n O ( m 2 ) . © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2008