On the Simplex Method for 0/1-Polytopes

• 成果类型: Article
• 署名作者: Black, Alexander E.; De Loera, Jestis A.; Kafer, Sean; Sanita, Laura
• 署名单位: University of California System; University of California Davis; University System of Georgia; Georgia Institute of Technology; Bocconi University
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2021.0345
• 发表日期: 2025
• 关键词: monotonic diameter; hirsch conjecture; algorithms; complexity; polytopes

摘要

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.