Paper Info
Title
An Improved Version of the Random-Facet Pivoting Rule for the Simplex Algorithm
Abstract
The Random-Facet pivoting rule of Kalai and of Matousek, Sharir and Welzl is an elegant randomized pivoting rule for the simplex algorithm, the classical combinatorial algorithm for solving linear programs (LPs). The expected number of pivoting steps performed by the simplex algorithm when using this rule, on any linear program involving n inequalities in d variables, is 2O(√{(n-d),log({d}/{√{n-d}}},), where log n=max{1,log n}. A dual version of the algorithm performs an expected number of at most 2O(√{d,log({(n-d)}/√d},) dual pivoting steps. This dual version is currently the fastest known combinatorial algorithm for solving general linear programs. Kalai also obtained a primal pivoting rule which performs an expected number of at most 2O(√d,log n) pivoting steps. We present an improved version of Kalai's pivoting rule for which the expected number of primal pivoting steps is at most min{2O(√(n-d),log(d/(n-d),)},2O(√{d,log((n-d)/d}},)}. This seemingly modest improvement is interesting for at least two reasons. First, the improved bound for the number of primal pivoting steps is better than the previous bounds for both the primal and dual pivoting steps. There is no longer any need to consider a dual version of the algorithm. Second, in the important case in which n=O(d), i.e., the number of linear inequalities is linear in the number of variables, the expected running time becomes 2O(√d) rather than 2O(√d log d). Our results, which extend previous results of Gartner, apply not only to LP problems, but also to LP-type problems, supplying in particular slightly improved algorithms for solving 2-player turn-based stochastic games and related problems.
Year
DOI
Venue
2015
10.1145/2746539.2746557
ACM Symposium on Theory of Computing
Keywords
Field
DocType
Linear programming,simplex algorithm,randomized pivoting rules
Binary logarithm,Discrete mathematics,Combinatorics,Simplex algorithm,Combinatorial algorithms,Expected value,Linear programming,Facet (geometry),Linear inequality,Mathematics
Conference
ISSN
Citations 
PageRank 
0737-8017
5
0.45
References 
Authors
44
2
Name
Order
Citations
PageRank
Thomas Dueholm Hansen116113.77
Uri Zwick23586257.02