It is our great pleasure to announce the Dutch Seminar on Optimization as a new initiative to bring together researchers from the Netherlands and beyond.
The goal of this initiative is to establish a new forum for the Dutch optimization community to come together, to help provide a spotlight for up and coming local talent, and to bring in high quality international speakers. The topics of the seminar are centered around Optimization in a broad sense, but with a focus on (though not limited to) the theoretical foundations of discrete and continuous optimization.
We would like to invite all researchers, especially also PhD students, who are working on related topics to join the events.
Speaker: Laura Sanita (TU Eindhoven)
Title: On the diameter and the circuit-diameter of polytopes
Abstract:
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.
