SPOC 25: Structure des polytopes
Primary tabs
Date:
Friday, 25 November, 2022
Inscription:
25ème séminaire du groupe POC
Le VENDREDI 25 NOVEMBRE 2023
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
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).
16h00 - 16h30