Title: An Introduction to the Circuits of Polyhedra, The Circuit Diameter, and Their Applications
| Speaker: | Sean Kafer |
| Affiliation: | University of Waterloo |
| Room: | MC 5417 |
Abstract:
The combinatorial diameter of a polyhedron P is the maximum value of a shortest path between two vertices of P, where the path moves along edges of P. Its study is motivated largely by its implications on the running time of the Simplex algorithm. In contrast, the circuit diameter of P is defined as the maximum value of a shortest path between two vertices of P, where the path moves along the circuits of P, where circuits are vectors that are parallel to a maximal set of facets of P. Equivalently, the set of circuits can be defined as the set of all edge directions that can be obtained by translating the facets of P. As such, the circuit diameter generalizes combinatorial diameter. Furthermore, circuits have the potential to be used to develop Simplex-like algorithms which solve LPs by moving along circuit directions.
This talk is intended as an introduction to the subject of circuits, the circuit diameter, and the application of circuits to augmentation algorithms. I will assume no foreknowledge of these topics. In addition to basics, I will discuss results about the circuit diameters of some well-known combinatorial polytopes. I will also discuss what is known about the potential for circuits to be used to solve LPs, including the best known performance of different "pivot rules" for circuit-based LP solving algorithms. Finally, I will discuss some hardness results regarding such algorithms, as well as hardness implications on the Simplex algorithm derived from results about circuits.
Some of this talk is based on work with coauthors Laura Sanità, Kostya Pashkovich, and Jesús De Loera.