Escaping Degeneracy by Following Shadow Edges

Abstract

The Simplex method is among the most widely used approaches for solving linear programs. Starting at a vertex solution of the feasible region, the algorithm proceeds through a sequence of basis exchanges (known as pivots), each corresponding to a move along an improving edge of the polyhedron toward a better vertex. A central challenge affecting the efficiency of the Simplex method is degeneracy, which can cause long sequences of pivot operations that fail to change the current vertex solution. In this paper, we prove the existence of a pivot rule which is able to escape degeneracy and follow any given shadow edge-direction when initialized at some compatible basis, with a linear number of degenerate Simplex pivots. As a byproduct of our result, we obtain an improved bound on the number of degenerate Simplex pivots needed to solve linear programs defined on 0/1 polytopes.

One-bubble solution with maximum points escaping to infinity for the energy-critical heat equation in ℝ⁵
Junichi Harada, Qidi Zhang
arXiv16 Sep 2026PreprintarXiv licenceFull textAnalysis & PDEsarXiv
Escaping and generics over ideals
Laurent Bienvenu, Noam Greenberg, Ludovic Patey +1
arXiv4 Nov 2026PreprintCC BY 4.0Full textLogic & foundationsarXivHAL
On the Hausdorff dimension of the set of non-escaping points in the Julia set
Walter Bergweiler, Weiwei Cui, Lingrui Wang
arXiv14 Sep 2026PreprintarXiv licenceFull textDynamical systemsarXiv
Dynamical (non-)recurrence of escaping exponential maps
Weiwei Cui, Jiaxing Huang, Jun Wang
arXiv3 Sep 2026PreprintarXiv licenceFull textAnalysis & PDEs Dynamical systemsarXiv
On the group of automorphisms of the escaping sets of Hénon maps
Mahima, Ratna Pal
arXiv19 Oct 2026PreprintarXiv licenceFull textAnalysis & PDEs Dynamical systemsarXiv

Cite

BibTeX RIS

BibTeX

@misc{black2026escaping,
  title = {{Escaping Degeneracy by Following Shadow Edges}},
  author = {Alexander E. Black and Sean Kafer and Laura Sanità},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.12130},
  eprint = {2610.12130},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.12130},
}

RIS

TY  - UNPB
TI  - Escaping Degeneracy by Following Shadow Edges
AU  - Alexander E. Black
AU  - Sean Kafer
AU  - Laura Sanità
PY  - 2026
DA  - 2026/10/08
PB  - arXiv
DO  - 10.48550/arxiv.2610.12130
UR  - https://arxiv.org/abs/2610.12130
AB  - The Simplex method is among the most widely used approaches for solving linear programs. Starting at a vertex solution of the feasible region, the algorithm proceeds through a sequence of basis exchanges (known as pivots), each corresponding to a move along an improving edge of the polyhedron toward a better vertex. A central challenge affecting the efficiency of the Simplex method is degeneracy, which can cause long sequences of pivot operations that fail to change the current vertex solution. In this paper, we prove the existence of a pivot rule which is able to escape degeneracy and follow any given shadow edge-direction when initialized at some compatible basis, with a linear number of degenerate Simplex pivots. As a byproduct of our result, we obtain an improved bound on the number of degenerate Simplex pivots needed to solve linear programs defined on 0/1 polytopes.
ER  -

Abstract

Related

Cite