The Klee-Minty random edge chain moves with linear speed

József Balogh, Robin Pemantle

Research output: Contribution to journalArticlepeer-review

Abstract

An infinite sequence of 0's and 1's evolves by flipping each 1 to a 0 exponentially at rate 1. When a 1 flips, all bits to its right also flip. Starting from any configuration with finitely many 1's to the left of the origin, we show that the leftmost 1 moves right with bounded speed. Upper and lower bounds are given on the speed. A consequence is that a lower bound for the run time of the random-edge simplex algorithm on a Klee-Minty cube is improved so as to be quadratic, in agreement with the upper bound.

Original languageEnglish (US)
Pages (from-to)464-483
Number of pages20
JournalRandom Structures and Algorithms
Volume30
Issue number4
DOIs
StatePublished - Jul 2007

Keywords

  • Binary
  • Bit
  • Ergodic
  • Flip
  • Markov chain
  • Simplex method

ASJC Scopus subject areas

  • Software
  • Mathematics(all)
  • Computer Graphics and Computer-Aided Design
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'The Klee-Minty random edge chain moves with linear speed'. Together they form a unique fingerprint.

Cite this