As announced earlier, Workshop "Polytope Diameter and Related Topics"
will be held online via Zoom on September 2, 2022.
If you are interested in joining the workshop, please register at the
following site.
https://uec-tokyo.zoom.us/meeting/register/tZ0qfuyrqDsiEtLvY3ud3jl__yCaiyWSYpDb
Below is our program (Time in CEST).
8:20- 8:30 Organizer: Introduction to the workshop
8:30- 9:30 Hariharan Narayanan: A Spectral Approach to Polytope Diameter
9:45-10:45 Vincent Pilaud: Diameters of generalizations of the
associahedron
11:00-12:00 Francisco Santos: TBA
12:00-14:00 Lunch and Free Discussion
14:00-15:00 Daniel Dadush: Asymptotic Bounds on the Combinatorial
Diameter of Random Polytopes
15:15-16:15 Jean Cardinal: Flip graphs and polytopes
16:30-17:30 Jesús De Loera: On Polyhedra Parametrizing ALL pivot
rules for the Simplex Method
For further detail, please visit the following website.
http://dopal.cs.uec.ac.jp/okamotoy/misc/2022/pdart.html
Thank you. We are looking forward to your participation.
Best regards,
Yoshio Okamoto
okamotoy@uec.ac.jp
On 2022/07/15 15:42, Yoshio Okamoto wrote:
> Call for Participation
> ===============================================================================
>
> 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
