Informatics Report Series


Report   

EDI-INF-RR-0467


Related Pages

Report (by Number) Index
Report (by Date) Index
Author Index
Institute Index

Home
Title:Random Walks on the Vertices of Transportation Polytopes with Constant Number of Sources
Authors: Mary Cryan ; Martin Dyer ; Haiko Muller ; Leen Stougie
Date:Jan 2003
Publication Title:Proceedings of SODA 2003 (ACM-SIAM Symposium on Discrete Algorithms)
Publisher:ACM/SIAM
Publication Type:Conference Paper Publication Status:Published
Page Nos:330-339
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},
}


Home : Publications : Report 

Please mail <reports@inf.ed.ac.uk> with any changes or corrections.
Unless explicitly stated otherwise, all material is copyright The University of Edinburgh