Random walks, totally unimodular matrices, and a randomised dual simplex algorithm

DOI10.1007/BF01582563zbMath0820.90066WikidataQ56324072 ScholiaQ56324072MaRDI QIDQ1330890

Martin Dyer, Alan M. Frieze

Publication date: 10 August 1994

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

zbMATH Keywords

random walkstotally unimodular matrixdiameter of polytopes

Mathematics Subject Classification ID

Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Linear programming (90C05)

Related Items

Improving bounds on the diameter of a polyhedron in high dimensions, Geometric random edge, Extended Formulations for Stable Set Polytopes of Graphs Without Two Disjoint Odd Cycles, Notes on \(\{a,b,c\}\)-modular matrices, On the Number of Distinct Rows of a Matrix with Bounded Subdeterminants, Linear programming, the simplex algorithm and simple polytopes, On circuit diameter bounds via circuit imbalances, A polynomial time primal network simplex algorithm for minimum cost flows, Recent progress on the combinatorial diameter of polytopes and simplicial complexes, Circuit walks in integral polyhedra, On the Combinatorial Diameters of Parallel and Series Connections, Some Problems on Approximate Counting in Graphs and Matroids, A Friendly Smoothed Analysis of the Simplex Method, On sub-determinants and the diameter of polyhedra, A scaling algorithm for optimizing arbitrary functions over vertices of polytopes, A note on non-degenerate integer programs with small sub-determinants, Random walks on the vertices of transportation polytopes with constant number of sources, On the shadow simplex method for curved polyhedra, GEOMETRIC BIJECTIONS FOR REGULAR MATROIDS, ZONOTOPES, AND EHRHART THEORY, Comments on: Recent progress on the combinatorial diameter of polytopes and simplicial complexes, Comments on: Recent progress on the combinatorial diameter of polytopes and simplicial complexes, On the recognition of \(\{a,b,c\}\)-modular matrices, An asymptotically improved upper bound on the diameter of polyhedra, Extended formulations for stable set polytopes of graphs without two disjoint odd cycles

Cites Work

• Approximate counting, uniform generation and rapidly mixing Markov chains
• Two combinatorial applications of the Aleksandrov-Fenchel inequalities
• The Hirsch conjecture is true for (0,1)-polytopes
• A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
• The Random Walk Construction of Uniform Spanning Trees and Uniform Labelled Trees
• Approximating the Permanent
• Efficiency of the Primal Network Simplex Algorithm for the Minimum-Cost Circulation Problem
• Theoretical Properties of the Network Simplex Method
• A random polynomial-time algorithm for approximating the volume of convex bodies
• A bad network problem for the simplex method and other minimum cost flow algorithms
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item