EUVIMEDEUVIMED entdecken
Crossref

On the Simplex Method for 0/1-Polytopes

Alexander E. Black, Jesús A. De Loera, Sean Kafer, Laura Sanità

Mathematics of Operations Research · 2025-05 · 50 (2) · 1398-1420

DOI: 10.1287/moor.2021.0345 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Mathematics of Operations Research, 2025-05. Verfasst von Alexander E. Black und 3 weiteren Autor:innen. Die Arbeit wurde bisher 7-mal zitiert (Crossref) und nennt 58 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We present three new pivot rules for the Simplex method for Linear Programs over 0/1-polytopes. We show that the number of nondegenerate steps taken using these three rules is strongly polynomial, linear in the number of variables, and linear in the dimension. Our bounds on the number of steps are asymptotically optimal on several well-known combinatorial polytopes. Our analysis is based on the geometry of 0/1-polytopes and novel modifications to the classical steepest-edge and shadow-vertex pivot rules. We draw interesting connections between our pivot rules and other well-known algorithms in combinatorial optimization. Funding: A. E. Black and J. A. De Loera are grateful for the support received through the National Science Foundation [Grants DMS-1818969 and NSF GRFP]. L. Sanita is grateful for the support received from the Nederlandse Organisatie voor Wetenschappelijk Onderzoek [Grant VI.Vidi.193.087].

Zitieren

APA

Black, A. E., Loera, J. A. D., Kafer, S., & Sanità, L. (2025). On the Simplex Method for 0/1-Polytopes. Mathematics of Operations Research, 50(2), 1398-1420. https://doi.org/10.1287/moor.2021.0345

Vancouver

Black AE, Loera JAD, Kafer S, Sanità L. On the Simplex Method for 0/1-Polytopes. Mathematics of Operations Research. 2025;50(2):1398-1420. doi:10.1287/moor.2021.0345

BibTeX
@article{Black2025,
  author = {Black, Alexander E. and Loera, Jesús A. De and Kafer, Sean and Sanità, Laura},
  title = {On the Simplex Method for 0/1-Polytopes},
  journal = {Mathematics of Operations Research},
  year = {2025},
  volume = {50},
  number = {2},
  pages = {1398--1420},
  doi = {10.1287/moor.2021.0345}
}
Kostenlos starten →