Kick-off seminar: Laura Sanita (TU Eindhoven)

The diameter of a polytope P is the maximum length of a shortest path
between a pair of vertices of P, when one is allowed to walk on the
edges (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.
A generalized notion of diameter, recently introduced in the
literature, is that of circuit-diameter, defined as the maximum length
of a shortest path between two vertices of P, where the path can use
all edge directions (called circuits) that can arise by translating
some of the facets of P.
In this talk, I will discuss some algorithmic and complexity results
related to the diameter and the circuit-diameter of polytopes,
highlighting important open questions.