SPOC 25: Structure des polytopes

Friday, 25 November, 2022

25ème séminaire du groupe POC


En présentiel (et hybride si on y arrive)

Au laboratoire LAMSADE (Université Paris-Dauphine)
Place du Maréchal de Lattre de Tassigny 75017 PARIS
Salle A711

Sur le thème

"Structure des polytopes: "


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


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


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
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).


16h00 - 16h30