Séminaire Lotharingien de Combinatoire, 93B.10 (2025), 12 pp.
Alexander E. Black, Niklas Lütjeharms and Raman Sanyal
From Linear Programming to Colliding Particles
Abstract.
Although simplices may appear trivial in the context of linear optimization, the
simplex algorithm, guided by a pivot rule, can exhibit remarkably intricate
dynamics on them when solving linear programs. 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.
Received: November 15, 2024.
Accepted: February 15, 2025.
Final version: April 1, 2025.
The following versions are available: