2002/04/03 by Bernd Gärtner · 49 citations
Mathematics · Computer Science · #Advanced Combinatorial Mathematics #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Simplex algorithm #Simplex #Combinatorics #Mathematics #Facet (psychology) #Omega #Simple (philosophy) #Class (philosophy) #Linear programming #Discrete mathematics #Algorithm #Computer science #Artificial intelligence
paper · doi:10.1002/rsa.10034
published in Random Structures and Algorithms 20(3), 353-381 (Wiley)
openalex publication_date 2002/04/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/05/21
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 (Ω(√ n)) 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 (n2 ) 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