Workshop "Polytope Diameter and Related Topics"

September 2, 2022
Online via Zoom

As a part of the research project "Fusion of Computer Science, Engineering and Mathematics Approaches for Expanding Combinatorial Reconfiguration" (head investigator: Takehiro Ito), we are going to organize Workshop "Polytope Diameter and Related Topics" via Zoom on September 2 (based on European Timezone), 2022.

A basic idea is to share fundamental concepts and recent trends of polytope diameter and related topics. The question on polytope diameter is closely related to the performance of a combinatorial algorithm such as the simplex method for linear programming. It is a big open problem whether there exists a combinatorial polynomial-time algorithm for linear programming while known polynomial-time algorithms such as the ellipsoid method and the interior-point methods are not considered combinatorial. Several algorithmic challenges in linear programming and integer programming rely on properties on "diameter". A celebrated conjecture by Hirsch states that the diameter of a convex polytope is bounded from above by the number of facets minus the dimension. The conjecture was disproved by Santos, but a question still remains that the diameter can be bounded by a polynomial of the number of facets and the dimension. Furthermore, several questions on combinatorial upper bounds for reconfiguration problems are related to polytope diameter. For example, the diameter of an associahedron is equal to the maximum flip distance between two triangulations of a convex polygon. A breakthrough result by Sleator, Tarjan and Thurston gave a lower bound for that diameter with hyperbolic geometry, which has been well-known in theoretical computer science since it is also related to the rotation distance between rooted trees.

This workshop aims at the broad audience of discrete mathematics and theoretical computer science, who wish to learn and work on this active research area.

The program will be exclusively composed of invited talks. Each talk is planned to span one hour, including discussion.

List of Confirmed Invited Speakers

in alphabetical order


Time in CEST

Talk Titles and Abstracts