Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2511.14244 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915969378549760 |
|---|---|
| author | Gibor, Daniel |
| author_facet | Gibor, Daniel |
| contents | 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} πk (1 + λH_n) \sqrt{d} n / 3 λ$. In the non-$k$-round case, we obtain a bound of $26 πt (1 + λH_n) \sqrt{d} n / λρ$. To achieve this, we provide a slightly lower bound of $3 \sqrt{2} λ/ (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) ε^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$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_14244 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Tighter Bounds for the Randomized Polynomial-Time Simplex Algorithm for Linear Programming Gibor, Daniel Computational Complexity Computational Geometry 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} πk (1 + λH_n) \sqrt{d} n / 3 λ$. In the non-$k$-round case, we obtain a bound of $26 πt (1 + λH_n) \sqrt{d} n / λρ$. To achieve this, we provide a slightly lower bound of $3 \sqrt{2} λ/ (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) ε^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$. |
| title | Tighter Bounds for the Randomized Polynomial-Time Simplex Algorithm for Linear Programming |
| topic | Computational Complexity Computational Geometry |
| url | https://arxiv.org/abs/2511.14244 |