Showing 2024Show all
3 papers · 1 filter
math.CO2024
Random Shadows of Fixed Polytopes
Alexander E. Black, Francisco Criado
Estimating the number of vertices of a two dimensional projection, called a shadow, of a polytope is a fundamental tool for understanding the performance of the shadow simplex meth…
math.CO2024
From linear programming to colliding particles
Alexander E. Black, Niklas Lütjeharms, Raman Sanyal
Although simplices are trivial from a linear optimization standpoint, the simplex algorithm can exhibit quite complex behavior. In this paper we study the behavior of max-slope piv…
math.OC2024
Exponential Lower Bounds for Many Pivot Rules for the Simplex Method
Alexander E. Black
The existence of a pivot rule for the simplex method that guarantees a strongly polynomial run-time is a longstanding, fundamental open problem in the theory of linear programming.…