Metraipolis › archive › dc_f5627d7bbe71

Escaping Degeneracy by Following Shadow Edges — arXiv:2610.12130

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.12130
License (as archived)
CC0-1.0
Archived
2026-10-09T06:28:07.950Z
SHA-256 of the archived text
4206919025f384c0fdf4c49888be2bb567ef7bf98584868192552e9b33658932
Stable URL of this page
https://metraipolis.com/documento/dc_f5627d7bbe71

How to cite

Escaping Degeneracy by Following Shadow Edges — arXiv:2610.12130 — arXiv (en), https://arxiv.org/abs/2610.12130 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_f5627d7bbe71 (Metraipolis archive dc_f5627d7bbe71, sha256 4206919025f384c0fdf4c49888be2bb567ef7bf98584868192552e9b33658932)
BibTeX
@misc{dcf5627d7bbe71,
  title = {Escaping Degeneracy by Following Shadow Edges — arXiv:2610.12130},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.12130},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_f5627d7bbe71; sha256 4206919025f384c0fdf4c49888be2bb567ef7bf98584868192552e9b33658932},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.12130. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.OC, nuovi lavori del giorno).
Categorie arXiv: Optimization and Control (math.OC) ; Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2610.12130 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-09T05:52:31.616Z dalla pagina https://arxiv.org/list/math.OC/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).