The Klee–Minty random edge chain moves with linear speed

DOI10.1002/rsa.20127zbMath1136.60305arXivmath/0506626OpenAlexW2949832463MaRDI QIDQ5297136

József Balogh, Robin Pemantle

Publication date: 18 July 2007

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

Full work available at URL: https://arxiv.org/abs/math/0506626

zbMATH Keywords

bitflipMarkov chainsimplex methodergodicbinary

Mathematics Subject Classification ID

Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Combinatorial probability (60C05) Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Extreme-point and pivoting methods (90C49)

Related Items (4)

Pivoting in linear complementarity: Two polynomial-time cases ⋮ Random edge can be exponential on abstract cubes ⋮ Comments on: Recent progress on the combinatorial diameter of polytopes and simplicial complexes ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The Klee–Minty random edge chain moves with linear speed