pith. sign in

arxiv: 2511.14244 · v3 · submitted 2025-11-18 · 💻 cs.CC · cs.CG

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

Daniel Gibor This is my paper

Pith reviewed 2026-05-17 21:04 UTC · model grok-4.3

classification 💻 cs.CC cs.CG
keywords randomized simplexlinear programmingshadow boundsquasi-convex optimizationpolynomial time algorithmsperturbation methods
0
0 comments X

The pith

Tighter bounds on shadow projections improve the success probability of a randomized simplex algorithm for linear programming.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper extends the randomized polynomial-time simplex method introduced by Kelner and Spielman. It derives stronger upper bounds on the expected number of edges in the two-dimensional shadow of a logarithmically perturbed polytope. These bounds are obtained through improved quasi-convex minimization and maximization estimates together with logarithmic rounding. The resulting modification of the algorithm achieves a higher probability that the artificial vertex and pivot rule behave as required. A reader would care because better theoretical guarantees can guide more efficient implementations of linear programming solvers.

Core claim

The central discovery is that applying improved quasi-convex properties and logarithmic rounding produces 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 this bound is 16 sqrt(2) pi k (1 + lambda H_n) sqrt(d) n / 3 lambda and in the non-k-round case it is 26 pi t (1 + lambda H_n) sqrt(d) n / lambda rho. A lower bound of 3 sqrt(2) lambda / (16 n sqrt(d)) is given for the expected edge length, and the artificial vertex construction holds with probability at least 1 - (d + 2) e^{-log n} when lambda equals c log n.

What carries the argument

The two-dimensional shadow plane onto which the perturbed polytope is projected, together with the quasi-convex bounds on the minimum and maximum of certain functions over the edges.

If this is right

  • The pivot rule holds with probability at least 3/4.
  • The desired initialization properties hold with higher probability.
  • The overall algorithm remains polynomial-time but with improved constants.
  • The expected number of edges is reduced compared to prior analyses.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • These tighter bounds may allow the algorithm to be applied to higher-dimensional problems with less computational overhead in practice.
  • Similar shadow techniques could be refined for other randomized geometric algorithms.
  • Testing the bounds on random polytopes would verify the improvements numerically.

Load-bearing premise

The improved quasi-convex bounds hold for the chosen logarithmic perturbation and the artificial vertex properties transfer with the stated higher probability.

What would settle it

An explicit construction of a polytope and perturbation where the expected shadow edge count exceeds 16 sqrt(2) pi k (1 + lambda H_n) sqrt(d) n / 3 lambda in the k-round case.

Figures

Figures reproduced from arXiv: 2511.14244 by Daniel Gibor.

Figure 1
Figure 1. Figure 1: The geometric view of the shadow of a polytope. [PITH_FULL_IMAGE:figures/full_fig_p006_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: A polytope P is in a k-near-isotropic position. If the polytope is not in a k-near-isotropic position, then it is contained within an ellipse. If the shadow-vertex method fails within a limited number of steps, we apply a coordinate that maps the ellipse to the unit ball, each failure of the shadow-vertex simplex algorithm reduces the volume of the polytope by at least half. In this way, the polytope moves… view at source ↗
Figure 3
Figure 3. Figure 3: Re-scaling if a polytope P is not in a k-near-isotropic position. In this case, the expected number of edges of the shadow of the polytope is at most 42πt(1 + λlog(n))√ dnλ−1ρ −1 , for the ρ ≤ √ 1 d perturbation (We define the ρ-perturbation of some unit vector u to be the random unit vector v chosen by choosing a θ ∈ [0, π], according to the restriction of the exponential distribution of expectation ρ to … view at source ↗
Figure 4
Figure 4. Figure 4: Some of the variables in our change of coordinates. Picture taken from [PITH_FULL_IMAGE:figures/full_fig_p011_4.png] view at source ↗
read the original abstract

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 \sqrt{2} \pi k (1 + \lambda H_n) \sqrt{d} n / 3 \lambda$. In the non-$k$-round case, we obtain a bound of $26 \pi t (1 + \lambda H_n) \sqrt{d} n / \lambda \rho$. To achieve this, we provide a slightly lower bound of $3 \sqrt{2} \lambda / (16 n \sqrt{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) \epsilon^2 / 2$. In the non-$k$-round case, we obtain a quasi-convex bound of $3.4 \epsilon^2 / \rho^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 $\lambda = 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$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript modifies the Kelner-Spielman (KS06) randomized simplex algorithm for linear programming. It applies logarithmic rounding to the polytope and a logarithmic perturbation with parameter lambda = c log n, together with log(k)-rounding, to claim tighter bounds on the expected number of edges in the two-dimensional shadow-plane projection of the perturbed polytope: 16 sqrt(2) pi k (1 + lambda H_n) sqrt(d) n / 3 lambda in the k-round case and 26 pi t (1 + lambda H_n) sqrt(d) n / lambda rho in the non-k-round case. It also reports improved quasi-convex bounds of (d-2) epsilon^2 / 2 and 3.4 epsilon^2 / rho^2, and asserts that the artificial-vertex construction succeeds with probability at least 1 - (d + 2) e^{-log n} while the pivot rule succeeds with probability at least 3/4.

Significance. If the central derivations hold, the work would strengthen the theoretical analysis of shadow-vertex simplex methods by supplying explicit tighter constants and a higher success probability. This could be of interest to researchers studying randomized algorithms for linear programming and polyhedral combinatorics, as it refines the KS06 framework with quasi-convex properties and logarithmic perturbations.

major comments (2)
  1. [Abstract and modification of KS06] Abstract and section describing the modification of KS06: the claim that lambda = c log n together with log(k)-rounding yields artificial-vertex success probability at least 1-(d+2)e^{-log n} while preserving the shadow-plane edge-length lower bound 3 sqrt(2) lambda / (16 n sqrt(d)) is stated without exhibiting the modified concentration argument that replaces the original exponential tail analysis of KS06. This step is load-bearing for both the higher-probability claim and the subsequent application of the quasi-convex bounds to obtain the new shadow-edge counts.
  2. [Quasi-convex bounds and shadow analysis] Quasi-convex bounds and shadow analysis: the improved bounds (d-2)epsilon^2/2 (k-round) and 3.4 epsilon^2/rho^2 (non-k-round) are applied on top of the logarithmic perturbation, yet the manuscript does not verify that these quasi-convex properties continue to hold and that the edge-length lower bound remains valid under the specific choice lambda = c log n. This assumption directly supports the final edge-count expressions and must be shown explicitly.
minor comments (2)
  1. [Abstract] The abstract introduces parameters H_n, rho, t, and k in the bound expressions without defining them; a brief parenthetical definition or forward reference would improve readability.
  2. [Modification section] The motivation for selecting lambda = c log n to achieve the target probability should be stated more explicitly to clarify that the final bounds are expressed in terms of this choice rather than derived independently.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their thorough review and valuable suggestions. We address the major comments point by point below. We agree that the manuscript would benefit from more explicit details on the adapted concentration arguments and the verification of quasi-convex properties under the logarithmic perturbation. We will revise the paper accordingly to include these elements.

read point-by-point responses

  1. Referee: [Abstract and modification of KS06] Abstract and section describing the modification of KS06: the claim that lambda = c log n together with log(k)-rounding yields artificial-vertex success probability at least 1-(d+2)e^{-log n} while preserving the shadow-plane edge-length lower bound 3 sqrt(2) lambda / (16 n sqrt(d)) is stated without exhibiting the modified concentration argument that replaces the original exponential tail analysis of KS06. This step is load-bearing for both the higher-probability claim and the subsequent application of the quasi-convex bounds to obtain the new shadow-edge counts.

    Authors: We appreciate the referee highlighting this gap in the presentation. The original KS06 analysis relies on exponential tail bounds for the random perturbations to establish the success probability of the artificial vertex construction. In our modification, by setting lambda = c log n and incorporating log(k)-rounding, the failure probability for each of the d+2 relevant events becomes at most e^{-log n} = n^{-1}, leading to the union bound of 1 - (d+2)/n. To preserve the edge length lower bound of 3 sqrt(2) lambda / (16 n sqrt(d)), the logarithmic scaling must be shown not to affect the minimum edge lengths in the shadow plane adversely. We will add a new subsection in the revision that provides the full modified concentration argument, adapting the tail analysis from KS06 to this logarithmic regime. This will explicitly derive both the improved success probability and confirm the edge-length bound remains valid. We believe this addition will address the concern and make the higher probability claim rigorous. revision: yes

  2. Referee: [Quasi-convex bounds and shadow analysis] Quasi-convex bounds and shadow analysis: the improved bounds (d-2)epsilon^2/2 (k-round) and 3.4 epsilon^2/rho^2 (non-k-round) are applied on top of the logarithmic perturbation, yet the manuscript does not verify that these quasi-convex properties continue to hold and that the edge-length lower bound remains valid under the specific choice lambda = c log n. This assumption directly supports the final edge-count expressions and must be shown explicitly.

    Authors: The quasi-convex bounds we derive for 1-quasi-concave minimization and 1-quasi-convex maximization are based on the general properties of the perturbed polytope and the shadow plane projection, and they hold as long as the perturbation ensures sufficient smoothness and the rounding is logarithmic. However, we acknowledge that an explicit check is needed to confirm these bounds apply without degradation when lambda is set to c log n. In the revision, we will include a lemma or proposition that verifies the quasi-convexity under this parameter choice, showing that the constants (d-2)/2 and 3.4/rho^2 remain valid, and that the edge-length lower bound is preserved. This will then directly justify the new shadow-edge count expressions: 16 sqrt(2) pi k (1 + lambda H_n) sqrt(d) n / 3 lambda for the k-round case and the corresponding non-k-round bound. We thank the referee for emphasizing the need for this explicit verification. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation relies on external KS06 base and claimed independent quasi-convex improvements

full rationale

The paper modifies the KS06 randomized simplex method by introducing a logarithmic perturbation with parameter lambda set to c log n (to ensure artificial-vertex success probability >= 1-(d+2)e^{-log n}) together with log(k)-rounding and new quasi-convex bounds of (d-2)epsilon^2/2 or 3.4 epsilon^2/rho^2. These choices are standard parameter tuning for high-probability guarantees rather than redefinitions or fits that force the final shadow-edge bounds by construction. The reported edge-count expressions (e.g., 16 sqrt(2) pi k (1 + lambda H_n) sqrt(d) n / (3 lambda)) are derived from the stated lower bound on expected edge length 3 sqrt(2) lambda / (16 n sqrt(d)) and the quasi-convex estimates; they do not reduce to the inputs tautologically. No self-citation load-bearing, no uniqueness theorem imported from the authors, and no renaming of known results as new organization. The analysis is therefore self-contained against the external KS06 benchmark once the new quasi-convex claims are granted.

Axiom & Free-Parameter Ledger

1 free parameters · 1 axioms · 0 invented entities

The central claims rest on the base randomized simplex construction from KS06, the validity of the new quasi-convex bounds, and the logarithmic perturbation model. No new entities are postulated.

free parameters (1)
  • lambda = c log n
    Set to c log n for independent exponentially distributed random variables to raise initialization and pivot success probabilities.
axioms (1)
  • domain assumption Improved 1-quasi-concave minimization and 1-quasi-convex maximization bounds hold under the logarithmic rounding.
    Invoked to replace earlier looser constants with (d-2) epsilon^2 / 2 and 3.4 epsilon^2 / rho^2.

pith-pipeline@v0.9.0 · 5688 in / 1508 out tokens · 56239 ms · 2026-05-17T21:04:08.745024+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

19 extracted references · 19 canonical work pages

  1. [1]

    Maximization of linear function of variables subject to linear inequalities

    ref:1 George Bernard Dantzig. Maximization of linear function of variables subject to linear inequalities. In T. C. Koopmans, editor, Activity Analysis of Production and Allocation, pages 339 - 347. 1951

    work page 1951

  2. [2]

    Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time

    ref:2 Daniel Spielman, Shang - Hua Teng. Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time. In Proceeding of the thirty - third annual ACM symposium on Theory of computing, pages 296 - 305. 2001

    work page 2001

  3. [3]

    ref:3 Viktor Klee, George J. Minty. How Good Is the Simplex Algorithm? In O. Siska editor, Inequalities III Academic Press, pages 159 - 175. 1972

    work page 1972

  4. [4]

    Linear programming, the simplex algorithm and simple polytopes

    ref:4 Gil Kalai. Linear programming, the simplex algorithm and simple polytopes. In Mathematical Programming 79, pages 217 - 233. 1997

    work page 1997

  5. [5]

    A polynomial algorithm in linear programming

    ref:5 Leonid Genrikhovich Kachiyan. A polynomial algorithm in linear programming. In Doklady Akademii nauk SSSR, volume 244, number 5, pages 1093 - 1096. 1979

    work page 1979

  6. [6]

    A new polynomial time algorithm for linear programming

    ref:6 Narendra Karmarkar. A new polynomial time algorithm for linear programming. In Combinatorica 4, pages 373 - 395, 1984

    work page 1984

  7. [7]

    The dual method of solving the linear programming problem

    ref:7 Carlton Edward Lemke. The dual method of solving the linear programming problem. In Naval Research Logistics Quarterly, volume 1, pages 36 - 47. 1954

    work page 1954

  8. [8]

    Criss-cross methods: A fresh view on pivot algorithms

    ref:8 Komei Fukuda, Tam\' a s Terlaky. Criss-cross methods: A fresh view on pivot algorithms. In Mathematical Programming, volume 79, pages 269 - 395. 1997

    work page 1997

  9. [9]

    The existence of a short sequence of admissible pivots to an optimal basis in LP and LCP

    ref:9 Komei Fukuda, Hans - Jakob L\" u thi, Makoto Namiki. The existence of a short sequence of admissible pivots to an optimal basis in LP and LCP. In International Transactions in Operational Research, volume 4, issue 4, pages 273 - 284. 1997

    work page 1997

  10. [10]

    Kelner, Daniel A

    ref:10 Johnathan A. Kelner, Daniel A. Spielman. A randomized polynomial - time simplex algorithm for linear programming. In Proceedings of the thirty - eight annual ACM symposium on Theory of computing (STOC'06), pages 51 - 60. 2006

    work page 2006

  11. [11]

    Kelner, Evdokia Nikolova

    ref:11 Jonathan A. Kelner, Evdokia Nikolova. On the hardness and smoothed complexity of quasi - concave minimization. In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07), pages 472 - 482. 2007

    work page 2007

  12. [12]

    Kelner, Matthew Brand, Michael Mitzenmacher

    ref:12 Evdokia Velinova Nikolova, Johnathan A. Kelner, Matthew Brand, Michael Mitzenmacher. Stochastic shortest paths via quasi - convex maximization. In European Symposium on Algorithms, pages 552 - 563. 2006

    work page 2006

  13. [13]

    Smoothed Analysis of the Simplex Method

    ref:13 Daniel Dadush, Sophie Huiberts. Smoothed Analysis of the Simplex Method. In Tim Roughgarden, editor, Beyound Worst Case Analysis, pages 309 - 330. 2020

    work page 2020

  14. [14]

    artner, Martin Henk, G\

    ref:14 Bernard G\"artner, Martin Henk, G\"unter Ziegler. Randomized simplex algorithms on Klee - Minty cubes. In Combinatorica, volume 19, pages 349 - 372. 1998

    work page 1998

  15. [15]

    Linear Programming

    ref:15 Va s ek Chv\' a tal. Linear Programming. Edited by W. H. Freeman. 1983

    work page 1983

  16. [16]

    Optimality and degeneracy in linear programming

    ref:16 Abraham Charnes. Optimality and degeneracy in linear programming. In Econometrica, volume 20, pages 160 - 170. 1952

    work page 1952

  17. [17]

    Chandrasekaran

    ref:17 Nimrod Megiddo, R. Chandrasekaran. On the epsilon - perturbation method for avoiding degeneracy. In Operations Research Letters, volume 8, pages 305 - 308. 1989

    work page 1989

  18. [18]

    Spielman

    ref:18 Amit Deshpande, Daniel A. Spielman. Improved smoothed analysis of the shadow vertex simplex method. In 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05), pages 349 - 356. 2005

    work page 2005

  19. [19]

    Theory of Convex Bodies

    ref:19 Tommy Bonnesen Moritz, Werner Fenchel. Theory of Convex Bodies. In BSC Associates, Moscow, Idaho (U.S.). 1988

    work page 1988