# Poster Session Abstracts

## The simplex algorithm on transportation and network flow polytopes

### Edward D. Kim, J. De Loera, S. Onn, F. Santos

The simplex algorithm of George Dantzig is widely considered one of the top ten algorithms of the century. Given a convex polytope $P$, an initial vertex of $P$, and a linear functional $c$, the simplex algorithm finds a vertex optimizing $c$ by following a path on the graph of $P$ that is monotone on $c$. The simplex path travels from vertex to vertex on the polytope, with ambiguities on the choice of the next vertex resolved by a pivot rule. Under essentially every known pivot rule, the theoretical number of simplex iterations needed is exponential due to some well-engineered yet peculiar examples. However, the algorithm is highly efficient in practice on most linear optimization problems.