Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

The combinatorial diameter of a polytope 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 to solve linear programs (LP’s). 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 uses potential edge directions of P i.e., all edge directions that can be obtained by translating the facets of P. Such directions are called the circuits of P.

In this talk, I will present a characterization of the circuit diameter of some polytopes corresponding to classical combinatorial optimization problems, such as the Matching polytope and Traveling Salesman polytope. I will further give a complete characterization of the circuits of the Fractional Matching polytope, and use that to derive some hardness of computation results. Specifically, De Loera, Hemmecke, and Lee recently studied the potential use of circuits to develop Simplex-like algorithms to solve LP’s. They propose an augmentation procedure which iteratively finds better feasible solutions by moving along circuits, and they propose three different oracles for choosing a circuit at each step. We prove that two of these oracles are NP-hard to compute.

The first part of the talk is based on a joint work with K. Pashkovich and L. Sanità, while the second part is based on a joint work with J. De Loera and L. Sanità.