abstract
The \RF\ algorithm is a randomized variant of the simplex method
which is known
to solve any linear program with $n$ variables and $m$ constraints
using an expected number of pivot steps which is \emph{subexponential}
in both $n$ and $m$. This is the theoretically fastest simplex
algorithm known to date if $m\approx n$; it provably beats most of
the classical deterministic variants
which require $\exp(\Omega(n))$ pivot steps in the worst case.
\RF\ has independently been discovered and analyzed
ten years ago by Kalai as a variant of the primal simplex method, and
by Matou\v{s}ek, Sharir and Welzl in a dual form.
The essential ideas and results connected to \RF\ can be presented in a
particularly simple and instructive way for the case of linear programs
over \emph{combinatorial $n$-cubes}. I derive an explicit
upper bound of
\[\sum_{\ell=1}^n\frac{1}{\ell!}{n\choose\ell}\leq\exp(2\sqrt{n})-1\]
on the expected number of pivot
steps in this case, using a new technique of ``fingerprinting''
pivot steps. This bound also holds for
\emph{generalized} linear programs, similar flavors of which have
been introduced and studied by several researchers.
I then review an interesting class of generalized linear programs,
due to Matou\v{s}ek, showing that \RF\ may indeed require an expected
number of $\exp(\Omega(\sqrt{n}))$ pivot steps in the worst case.
The main new result of the paper is a proof that all actual linear programs in
Matou\v{s}ek's class are solved by \RF\ with an expected polynomial
number of $O(n^2)$ pivot steps. This proof exploits a combinatorial
property of linear programming which has only recently been discovered
by Holt and Klee. The result establishes the first scenario in which
an algorithm that works for generalized linear programs ``recognizes''
proper linear programs. Thus, despite Matou\v{s}ek's worst-case
result, the question remains open whether \RF\ (or any other simplex
variant) is a polynomial-time algorithm for linear programming.
Finally, I briefly discuss extensions of the combinatorial cube
results to the general case.
Back to the publications page
