===============================================================================
Workshop "Polytope Diameter and Related Topics"
September 2, 2022
Online via Zoom
http://dopal.cs.uec.ac.jp/okamotoy/misc/2022/pdart.html
===============================================================================
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 cerebrated
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.
*Registration*
The workshop is held as a Zoom meeting. If you are interested in
participation, please register yourself at the following site.
https://uec-tokyo.zoom.us/meeting/register/tZ0qfuyrqDsiEtLvY3ud3jl__yCaiyWSYpDb
After registration, the detail will be sent as an email.
Participation is free of charge.
*List of Confirmed Invited Speakers (in alphabetical order)*
-Jean Cardinal (Université Libre de Bruxelles, Belgium)
-Daniel Dadush (CWI, the Netherlands)
-Jesús De Loera (University of California, Davis, CA, USA)
-Hariharan Narayanan (Tata Institute of Fundamental Research, India)
-Vincent Pilaud (CNRS and École Polytechnique, France)
-Francisco Santos (University of Cantabria, Spain)
Program and the talk titles will be announced later.
*Organizer*
-Yoshio Okamoto (The University of Electro-Communications, Japan)
okamotoy@uec.ac.jp
If you have an inquiry, please send it to the organizer.
--
Yoshio Okamoto, Prof. <okamotoy@uec.ac.jp>
Dept. of Computer and Network Engineering
University of Electro-Communications
Chofugaoka 1-5-1, Chofu, Tokyo 182-8585
**********************************************************
*
* Contributions to be spread via DMANET are submitted to
*
* DMANET@zpr.uni-koeln.de
*
* Replies to a message carried on DMANET should NOT be
* addressed to DMANET but to the original sender. The
* original sender, however, is invited to prepare an
* update of the replies received and to communicate it
* via DMANET.
*
* DISCRETE MATHEMATICS AND ALGORITHMS NETWORK (DMANET)
* http://www.zaik.uni-koeln.de/AFS/publications/dmanet/
*
**********************************************************
Posts
