AarXiv18 Nov 2025

Tighter Bounds for the Randomized Polynomial-Time Simplex Algorithm for Linear Programming

Daniel Gibor

Abstract

In this paper, 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].]

A figure from Tighter Bounds for the Randomized Polynomial-Time Simplex Algorithm for Linear Programming — fig. from the paper

§ The Valyu brief

The paper, in five minutes

Read from the full text via Valyu Contents

A randomized polynomial-time simplex algorithm with tighter bounds and higher success probability is proposed.

What’s new

i.Introduced improved quasi-convex properties and logarithmic rounding/perturbation for the simplex algorithm.
ii.Derived tighter analytical bounds for the expected number of edges in the shadow projection of a perturbed polytope.
iii.Provided tighter bounds for 1‑quasi‑concave minimization and 1‑quasi‑convex maximization.
iv.Modified the Kelner‑Spielman randomized simplex algorithm to achieve a higher success probability.

How they did it

The work builds on the Kelner‑Spielman randomized polynomial‑time simplex method, applying enhanced quasi‑convex analysis, logarithmic rounding, and perturbation techniques to derive new bounds. Analytical calculations yield explicit formulas for edge‑count expectations and success probabilities. The algorithm is then adjusted with a new λ = c·log n and log(k)‑rounding to improve reliability.

What they found

k‑round case bound: 16 √2 π k (1+λ H_n) √d n / (3 λ).
Non‑k‑round case bound: 26 π t (1+λ H_n) √d n / (λ ρ).
Lower bound on expected edge length: 3 √2 λ / (16 n √d).
Quasi‑convex bound (k‑round): (d‑2) ε² / 2; (non‑k‑round): 3.4 ε² / ρ².
Success probability ≥ 1 − (d+2), e^{−log n}; pivot rule probability ≥ 3/4.

§ The Valyu brief

Reading the full paper and taking notes. This takes a few seconds…

§ Ask this paper

Ask a question about this paper

Valyu reads the full text and answers from what the paper actually says.

§ Related work in other archives

Tighter Bounds for the Randomized Polynomial-Time Simplex Algorithm for Linear Programming

The paper, in five minutes

Ask a question about this paper

Similar papers in all four archives

The paper, in five minutes

Similar papers in all four archives