The Random‐Facet simplex algorithm on combinatorial cubes

Abstract

Abstract The R ANDOM ‐F ACET 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 subexponential in both n and m. This is the theoretically fastest simplex algorithm known to date if m ≈ n; it provably beats most of the classical deterministic variants which require exp(Ω( n )) pivot steps in the worst case. R ANDOM ‐F ACET has independently been discovered and analyzed ten years ago by Kalai as a variant of the primal simplex method, and by Matous̆ek, Sharir, and Welzl in a dual form. The essential ideas and results connected to R ANDOM ‐F ACET can be presented in a particularly simple and instructive way for the case of linear programs over combinatorial n ‐ cubes. I derive an explicit upper bound of on the expected number of pivot steps in this case, using a new technique of “fingerprinting” pivot steps. This bound also holds for 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 Matous̆ek, showing that R ANDOM ‐F ACET may indeed require an expected number of $\exp \bigl(\Omega\bigl(\sqrt n\bigr)\bigr)$ pivot steps in the worst case. The main new result of the paper is a proof that all actual linear programs in Matous̆ek's class are solved by R ANDOM ‐F ACET with an expected polynomial number of $O \bigl(n^2 \bigr)$ 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 Matous̆ek's worst‐case result, the question remains open whether R ANDOM ‐F ACET (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. © 2002 Wiley Periodicals, Inc. Random Struct. Alg., 20:353–381, 2002