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

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

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

Full text

Pdf (900 KB)

Source

Symposium on Discrete Algorithms archive
Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms table of contents

Baltimore, Maryland

SESSION: Session 5B table of contents

Pages: 330 - 339

Year of Publication: 2003

ISBN:0-89871-538-5

Authors

Mary Cryan	University of Leeds, Leeds, England
Martin Dyer	University of Leeds, Leeds, England
Haiko Müller	University of Leeds, Leeds, England
Leen Stougie	Eindhoven University of Technology, the Netherlands and CWI Amsterdam, the Netherlands

Sponsors

: SIAM Activity Group on Discrete Mathematics
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Society for Industrial and Applied Mathematics Philadelphia, PA, USA

Bibliometrics

Downloads (6 Weeks): 8, Downloads (12 Months): 36, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

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 n^O(m2).

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	M. Balinski, On the graph structure of convex polyhedra in n-space. Pacific Journal of Mathematics, 11, pp. 431--434, 1961.
	2	Mary Cryan , Martin E. Dyer , Leslie Ann Goldberg , Mark Jerrum , Russell A. Martin, Rapidly Mixing Markov Chains for Sampling Contingency Tables with a Constant Number of Rows, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.711-720, November 16-19, 2002
	3	P. Diaconis and A. Gangolli, Rectangular arrays with fixed margins, in: D. Aldous, P.P. Varaiya, J. Spencer and J.M. Steele (Eds.), Discrete Probability and Algorithms, IMA Volumes on Mathematics and its Appfications, 72, Springer, New York, 1995, pp. 15--41.
	4	P. Diaconis, R.L. Graham, and J.A. Morrison, Asymptotic analysis of a random walk on a hypercube with many dimensions. Random Structures and Algorithms, 1, 1990, pp. 51--72.
	5	P. Diaconis and L. Saloff-Coste, Comparison theorems for reversible Markov chains. The Annals of Applied Probability, 3(3), 1993, pp. 696--730.
	6	P. Diaconis and D. Stroock, Geometric bounds for eigenvalues of Markov chains. The Annals of Applied Probability, 1, 1991, pp. 36--61.
	7	M.E. Dyer, The complexity of vertex enumeration methods. Mathematics of Operations Research, 8(3), 1983, pp. 381--402.
	8	Martin Dyer , Catherine Greenhill, Polynomial-time counting and sampling of two-rowed contingency tables, Theoretical Computer Science, v.246 n.1-2, p.265-278, Sept 2000 [doi>10.1016/S0304-3975(99)00136-X]
	9	Martin Dyer , Ravi Kannan , John Mount, Sampling contingency tables, Random Structures & Algorithms, v.10 n.4, p.487-506, July 1997 [doi>10.1002/(SICI)1098-2418(199707)10:4<487::AID-RSA4>3.0.CO;2-Q]
	10	G. Hadley, Transportation Problems (Chapter 9). Linear Programming, Addison-Wesley, Massachusetts, 1962, pp. 273--330.
	11	Gil Kalai, Polytope skeletons and paths, Handbook of discrete and computational geometry, CRC Press, Inc., Boca Raton, FL, 1997
	12	V. Klee and C. Witzgall, Facets and Vertices of Transportation Polytopes. In Mathematics of the Decision Sciences, Part 1, G.B Dantzig and A.F. Veinott (Eds.), American Mathematical Society, 1968, pp 257--282.
	13	C. McDiarmid, On the method of bounded differences. London Math. Soc. Lecture Note Series141, Cambridge University Press, 1989, pp. 148--188.
	14	Ben Morris, Improved Bounds for Sampling Contingency Tables, Proceedings of the Third International Workshop on Approximation Algorithms for Combinatorial Optimization Problems: Randomization, Approximation, and Combinatorial Algorithms and Techniques, p.121-129, August 08-11, 1999
	15	Benjamin James Morris , Alistair Sinclair, Random walks in convex sets, 2000
	16	Ben Morris , Alistair Sinclair, Random Walks on Truncated Cubes and Sampling 0-1 Knapsack Solutions, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.230, October 17-18, 1999
	17	I. Pak, Four questions on Birkhoff polytope. Annals of Combinatorics, 4, 2000, pp. 83--90.
	18	Igor Pak, On the number of faces of certain transportation polytopes, European Journal of Combinatorics, v.21 n.5, p.689-694, July 2000 [doi>10.1006/eujc.1999.0392]
	19	D. Randall and P. Tetali, Analyzing Glauber dynamics by comparison of Markov chains. Journal of Mathematical Physics, 41, 2000, pp. 1598--1615.
	20	A.J. Sinclair, Improved bounds for mixing rates of Markov chains and multicommodity flow. Combinatorics, Probability and Computing, 1, 1992, pp. 351--370.
	21	G. M. Ziegler. Lectures on polytopes. Graduate Texts in Mathematics152, Springer-Vedag, 1995.