This event is open to the public and registration is not required.

Abstract

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 Asaf Levin (Technion), George Manoussakis (Versailles), Syed Meesum (Wrocław), Shmuel Onn (Technion), and Lionel Pounin (Paris XIII).

Speaker Bio

Since 2004, Antoine Deza has been at McMaster University where he has held a Canada Research Chair in Combinatorial Optimization. Since 2008, he has been the Head of the Advanced Optimization Laboratory, and the Associate Director of MacDATA Institute since 2018. He had previously held a faculty position at the Tokyo Institute of Technology. He has been the Chair of the Fields Institute Industrial Optimization Seminar since 2008, and an Associate Editor for Discrete Applied Mathematics and Optimization Letters. He was elected a Fields Institute Fellow in 2014. He has held visiting positions at Ecole Polytechnique Fédérale de Lausanne, Technion Haifa, Tokyo Institute of Technology, Université Paris Sud, where he has held a Digiteo Chair in Combinatorics and Optimization, Université Pierre et Marie Curie, and Ecole Nationale des Ponts et Chaussées, Paris.

The Operations Research (OR) seminar series brings together graduate students, faculty and researchers from the University of Toronto community to interact with prominent scholars in the field of OR. Seminars feature visiting scholars from around the world as well as professors and post-docs. Topics include all variants of OR theory and their applications. Questions? Contact Merve Bodur at bodur@mie.utoronto.ca