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

M. Cryan, M. Dyer, H. Müller, L. Stougie

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

1 Citaat (Scopus)

Samenvatting

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).
Originele taal-2Engels
Pagina's (van-tot)333-355
TijdschriftRandom Structures and Algorithms
Volume33
Nummer van het tijdschrift3
DOI's
StatusGepubliceerd - 2008

Vingerafdruk

Duik in de onderzoeksthema's van 'Random walks on the vertices of transportation polytopes with constant number of sources'. Samen vormen ze een unieke vingerafdruk.

Citeer dit