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
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom