Random Walks on the Vertices of Transportation Polytopes with Constant Number of Sources

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 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).
Original languageEnglish
Title of host publicationProceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms
Place of PublicationPhiladelphia, PA, USA
PublisherSociety for Industrial and Applied Mathematics
Pages330-339
Number of pages10
ISBN (Print)0-89871-538-5
Publication statusPublished - 2003

Publication series

NameSODA '03
PublisherSociety for Industrial and Applied Mathematics

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