- 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 multi-commodity flow technique of Sinclair together with ideas developed by Morris and Sinclair for the knapsack problem, and Cryan et al. for contingency tables, to establish that the random walk approaches the uniform distribution in time n^{O(m^2)}.
- Links To Paper
- This is the ACM (publisher) webpage for this paper
- Mary Cryan's webpage, which has a .ps copy of the paper
- Bibtex format
- @InProceedings{EDI-INF-RR-0467,
- author = {
Mary Cryan
and Martin Dyer
and Haiko Muller
and Leen Stougie
},
- title = {Random Walks on the Vertices of Transportation Polytopes with Constant Number of Sources},
- book title = {Proceedings of SODA 2003 (ACM-SIAM Symposium on Discrete Algorithms)},
- publisher = {ACM/SIAM},
- year = 2003,
- month = {Jan},
- pages = {330-339},
- url = {http://portal.acm.org/citation.cfm?id=644163&jmp=cit&coll=portal&dl=ACM&CFID=58893700&CFTOKEN=94022534#CIT},
- }
|
