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

Cryan Mary | Zendy; Dyer Martin | Zendy; Müller Haiko | Zendy; Stougie Leen | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

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

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research