An Improved Version of the Random-Facet Pivoting Rule for the Simplex Algorithm

Random-Facet is a randomized pivoting rule for the simplex algorithm used to solve linear programming (LP) problems. It was devised independently by Kalai and by Matousek, Sharir and Welzl. It solves any LP problem using a sub-exponential number of pivoting steps, making it the fastest known pivoting rule for the simplex algorithm. We present a slightly improved version of this pivoting rule. Using the new pivoting rule, a linear program composed of O(d) constraints in d variables can be solved using an expected number of 2^{O(\sqrt{d})} pivoting steps, improving the previous bound of 2^{O(\sqrt{d\log d})}.

Joint work with Thomas Dueholm Hansen.