Premium
The Klee–Minty random edge chain moves with linear speed
Author(s) -
Balogh József,
Pemantle Robin
Publication year - 2007
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20127
Subject(s) - mathematics , combinatorics , upper and lower bounds , bounded function , enhanced data rates for gsm evolution , cube (algebra) , simplex , quadratic equation , simplex algorithm , geometry , mathematical analysis , algorithm , computer science , linear programming , telecommunications
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. © 2006 Wiley Periodicals, Inc. Random Struct. Alg., 2007