- This event has passed.
Eindhoven SPOR Seminar
Sep 29, 2020, 15:45 - 16:45
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.