Back to Search
Start Over
From linear programming to colliding particles
- Publication Year :
- 2024
-
Abstract
- 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 pivot rules on (products of) simplices and describe the associated pivot rule polytopes. For simplices, the pivot rule polytopes are combinatorially isomorphic to associahedra. To prove this correspondence, we interpret max-slope pivot rules in terms of the combinatorics of colliding particles on a line. For prisms over simplices, we recover Stasheff's multiplihedra. For products of two simplices we get new realizations of constrainahedra, that capture the combinatorics of certain particle systems in the plane.<br />Comment: 20 pages, 13 figures
- Subjects :
- Mathematics - Combinatorics
90C05, 90C57, 52B12, 52B11
Subjects
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.2405.08506
- Document Type :
- Working Paper