2025/11/18 by Daniel Gibor, Gibor, Daniel
Computer Science · Mathematics · #Advanced Optimization Algorithms Research #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Computational Geometry (cs.CG) #FOS: Computer and information sciences #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.2511.14244
openalex publication_date 2025/11/18 · openalex created_date 2025/11/20 · openalex updated_date 2026/07/28
We present a randomized polynomial-time simplex algorithm with higher probability and tighter bounds for linear programming by applying improved quasi-convex properties, a logarithmic rounding on a given polytope and its logarithmic perturbation. We base our work on the first randomized polynomial-time simplex method by Jonathan A. Kelner and Daniel A. Spielman [KS06]. We obtain stronger bounds for the expected number of edges in the projection of a perturbed polytope onto a two-dimensional shadow plane. In the k-round case, we obtain a bound of 16 √(2) πk (1 + λHn) √(d) n / 3 λ. In the non-k-round case, we obtain a bound of 26 πt (1 + λHn) √(d) n / λρ. To achieve this, we provide a slightly lower bound of 3 √(2) λ/ (16 n √(d)) on the expected edge length that appears in the shadow. Another tool we employ is a tighter bound for 1-quasi-concave minimization and 1-quasi-convex maximization. In the k-round case, we obtain a quasi-convex bound of (d - 2) ε2 / 2. In the non-k-round case, we obtain a quasi-convex bound of 3.4 ε2 / ρ2. We propose a modification of the Kelner and Spielman randomized simplex algorithm (STOC'06) [KS06] that achieves a higher success probability. To accomplish this, we apply our tighter bounds with a new expected value of λ= c log n for independent exponentially distributed random variables and with log(k)-rounding. The desired properties resulting from the construction of an artificial vertex during initialization hold with a higher probability of at least 1 - (d + 2), e-log n. The pivot rule of the randomized simplex modification holds with a probability of at least 3/4.