Random walks on the vertices of transportation polytopes with constant number of sources
From MaRDI portal
Publication:3608299
DOI10.1002/rsa.20222zbMath1193.05149WikidataQ56323850 ScholiaQ56323850MaRDI QIDQ3608299
Martin Dyer, Haiko Müller, Mary Cryan, Leen Stougie
Publication date: 4 March 2009
Published in: Random Structures and Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/rsa.20222
60G50: Sums of independent random variables; random walks
90B15: Stochastic network models in operations research
90C08: Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.)
05C38: Paths and cycles
05C81: Random walks on graphs
Cites Work
- Unnamed Item
- Unnamed Item
- On the graph structure of convex polyhedra in \(n\)-space
- Geometric bounds for eigenvalues of Markov chains
- A linear bound on the diameter of the transportation polytope
- A strongly polynomial minimum cost circulation algorithm
- Comparison theorems for reversible Markov chains
- Random walks, totally unimodular matrices, and a randomised dual simplex algorithm
- A polynomial time primal network simplex algorithm for minimum cost flows
- An application of Harnack inequalities to random walk on nilpotent quotients
- On the number of faces of certain transportation polytopes
- Polynomial-time counting and sampling of two-rowed contingency tables
- Four questions on Birkhoff polytopes
- Analyzing Glauber dynamics by comparison of Markov chains
- Asymptotic analysis of a random walk on a hypercube with many dimensions
- The Complexity of Vertex Enumeration Methods
- Rapidly Mixing Markov Chains for Sampling Contingency Tables with a Constant Number of Rows
- Approximate counting by dynamic programming
- Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow
- Sampling contingency tables
- Random Walks on Truncated Cubes and Sampling 0-1 Knapsack Solutions
- The Distribution of a Product from Several Sources to Numerous Localities
