Department of Computer Science | Institute of Theoretical Computer Science

Theory of Combinatorial Algorithms

Prof. Emo Welzl

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