Antoine Deza's seminar at CNRS LIX Ecole Polytechnique, 4 march 2019, 14:30

Dear all,

please note that Antoine Deza, professor at McMaster University (CA) will give a DASCIM seminar at LIX, in Salle Philippe Flajolet, at 14:30.

Yours

Leo

--

Algorithmic, combinatorial, and geometric aspects of linear optimization

The simplex and interior point methods are currently the most computationally successful algorithms for linear optimization. While the simplex methods follow an edge path, the interior point methods follow the central path. The algorithmic issues are closely related to the combinatorial and geometric structure of the feasible region. Focusing on the analysis of worst-case constructions leading to computationally challenging instances, we discuss connections to the largest diameter of lattice polytopes, to the complexity of convex matroid optimization, and to the number of generalized retarded functions in quantum field theory.  Complexity results and open questions are also presented. In particular, we answer a question raised in 1986 by Colbourn, Kocay, and Stinson by showing that deciding whether a given sequence is the degree sequence of a 3-hypergraph is computationally prohibitive.

Based on joint works with Anna Deza (Toronto), Joe Guan (McMaster), Asaf Levin (Technion), George Manoussakis (Versailles), Syed Meesum (Wroc?aw), Shmuel Onn (Technion), and Lionel Pournin (Paris XIII).