Laura Sanità

On the hardness of computing the diameter of a polytope

The diameter of a polytope P is the maximum length of a shortest path between a pair of vertices on the 1-skeleton of P , which is the graph where the vertices correspond to the 0-dimensional faces of P, and the edges are given by the 1-dimensional faces of P. Despite decades of studies, it is still not known whether the diameter of a d-dimensional polytope with n facets can be bounded by a polynomial function of n and d. This is a fundamental open question in discrete mathematics, motivated by the (still unknown) existence of a polynomial pivot rule for the Simplex method for solving Linear Programs.
The diameter of a polytope has been studied from many different perspectives, including a computational complexity point of view. In this talk, I will show some hardness results, obtained by exploiting the structure of a well-known polytope in the optimization community: the fractional matching polytope.

Recorded Presentation