On the Simplex Method for 0/1-Polytopes
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.
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}
}
EUVIMED