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

DOI10.1002/RSA.20222MaRDI QIDQ3608299zbMATHOpenAlexWikidataFDO

Authors Mary Cryan, Martin Dyer, Haiko Müller, L. Stougie

Publication date 4 March 2009

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/rsa.20222

zbMATH Keywords

random walktransportation polytoperapid mixing

Mathematics Subject Classification ID

Sums of independent random variables; random walks (60G50) Paths and cycles (05C38) Random walks on graphs (05C81) Stochastic network models in operations research (90B15) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08)

Recommendations

• scientific article; zbMATH DE number 2079356
• Random walks on polytopes and an affine interior point method for linear programming
• Random walks on polytopes and an affine interior point method for linear programming
• Random walks on polytopes of constant corank
• Random walks in polytopes and negative dependence

Cites work

• scientific article; zbMATH DE number 2079356 (Why is no real title available?)
• scientific article; zbMATH DE number 3249566 (Why is no real title available?)
• A linear bound on the diameter of the transportation polytope
• A polynomial time primal network simplex algorithm for minimum cost flows
• A strongly polynomial minimum cost circulation algorithm
• An application of Harnack inequalities to random walk on nilpotent quotients
• Analyzing Glauber dynamics by comparison of Markov chains
• Approximate counting by dynamic programming
• Asymptotic analysis of a random walk on a hypercube with many dimensions
• Comparison theorems for reversible Markov chains
• Four questions on Birkhoff polytopes
• Geometric bounds for eigenvalues of Markov chains
• Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow
• On the graph structure of convex polyhedra in \(n\)-space
• On the number of faces of certain transportation polytopes
• Polynomial-time counting and sampling of two-rowed contingency tables
• Random Walks on Truncated Cubes and Sampling 0-1 Knapsack Solutions
• Random walks, totally unimodular matrices, and a randomised dual simplex algorithm
• Rapidly Mixing Markov Chains for Sampling Contingency Tables with a Constant Number of Rows
• Sampling contingency tables
• The Complexity of Vertex Enumeration Methods
• The Distribution of a Product from Several Sources to Numerous Localities

Cited in

(1)

• scientific article; zbMATH DE number 2079356 (Why is no real title available?)

This page was built for publication: Random walks on the vertices of transportation polytopes with constant number of sources

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3608299)