Date:

Friday, 25 November, 2022

Inscription:

**Le VENDREDI 25 NOVEMBRE 2023**

Au laboratoire LAMSADE (Université Paris-Dauphine)

Place du Maréchal de Lattre de Tassigny 75017 PARIS

Salle A711

Sur le thème

**Entrée gratuite
Merci de vous inscrire à cette journée pour faciliter l'organisation**

**Pour voir la liste des inscrits**

Programme de la journée:

**9h45-10h00** Accueil viennoiserie

**10h00-11h00**

**Part 1: Polyhedral combinatorics and combinatorial optimization**

** Lionel Pournin** LIPN, Université Sorbonne Paris Nord, France

The simplex and interior point methods are currently the most computationally successful algorithms for linear optimization. While simplex methods follow an edge path, interior point methods follow the central path. The complexity of these methods is closely related to the combinatorial and geometric structures of the feasible region. After reviewing a number of properties and open questions from polyhedral combinatorics, we will turn our attention to the link between the diameter of polyhedral graphs and the complexity of linear optimization. In particular, we will focus on the analysis of worst-case constructions leading to computationally challenging instances: recently obtained lower bounds on the largest possible diameter of lattice polytopes will be presented. These bounds, via lattice zonotopes, are established using tools from combinatorics and number theory.

This talk is based on joint work with Antoine Deza.

**11h00-11h30 Pause**

**11h30-12h30**

**Part 2: Polyhedral combinatorics and combinatorial optimization**

** Lionel Pournin** LIPN, Université Sorbonne Paris Nord, France

**12h30-14h00 Repas**

**14h00 - 15h00**

**The linear extension polytope of a poset
Jean-Paul DOIGNON** ULB, Belgique

The linear extension polytope of a poset P is the convex hull of the characteristic vectors of the linear extensions of P. It is a generalization of the linear ordering polytope, obtained for a poset with no comparability. A natural relaxation of the linear extension polytope, called the axiomatic relaxation, is the set of solutions of the linear inequalities encoding the axioms for linear extensions. It is natural to ask when the linear extension polytope of P equals its axiomatic relaxation. We show that this is the case precisely when the poset P has extension dimension at most 2 (as will be explained, the extension dimension is a variant of the dimension). We also characterize such posets P by a list of 78 forbidden induced subposets, and their comparability graphs by 2 forbidden subgraphs.

Joint work with Samuel Fiorini, Gwenaël Joret and Selim Rexhep

**15h00-15h30 Pause**

**15h30 - 16h00**

**Inapproximability of shortest paths on perfect matching polytopes**

**Jean CARDINAL** ULB, Belgique

We consider the computational problem of finding short paths in the skeleton of the perfect matching polytope of a bipartite graph. We prove that unless P = NP, there is no polynomial-time algorithm that computes a path of constant length between two vertices at distance two of the perfect matching polytope of a bipartite graph. This answers negatively a question posed by Ito, Kakimura, Kamiyama, Kobayashi and Okamoto [SIAM Journal on Discrete Mathematics, 36(2), pp. 1102-1123 (2022)]. Assuming the Exponential Time Hypothesis we prove the stronger result that there exists no polynomial-time algorithm computing a path of length at most (1/2 − o(1)) log n / log log n between two vertices at distance 2 of the perfect matching polytope of an n-vertex bipartite graph. These results remain true if the bipartite graph is restricted to be of maximum degree 3.The above has the following interesting implication for the performance of pivot rules for the simplex algorithm on simply-structured combinatorial polytopes: If P ̸= NP, then for every simplex pivot rule executable in polynomial time and every constant k ∈ N there exists a

linear program on a perfect matching polytope and a starting vertex of the polytope such that the optimal solution can be reached in two monotone steps from the starting vertex, yet the pivot rule will require at least k steps to reach the optimal solution. This result remains true if in addition so-called circuit pivots are allowed.

Joint work with Raphael Steiner (ETH Zurich).

**16h****00 - 16h30**