活动

Title:  Combinatorial and geometric aspects of optimization

Abstract: 

Worst-case constructions have helped providing a deeper understanding of how the structural properties of the input affect the computational performance of optimization algorithms. Recent examples include the construction of Allamigeon et al. for which the interior point method performs an exponential number of iterations. In a similar spirit, we investigate the following question: how close can two disjoint lattice polytopes contained in a fixed hypercube be? This question stems from various contexts where the minimal distance between such polytopes appears in complexity bounds of optimization algorithms. We provide nearly matching lower and upper bounds on this distance and discuss its exact computation. Based on joint work with Shmuel Onn, Sebastian Pokutta, and Lionel Pournin.

Biography:  Antoine Deza

Antoine Deza is the Head of Advanced Optimization Laboratory at McMaster University, Ontario, where he has held a Canada Research Chair in Combinatorial Optimization, and has been the Associate Director of MacDATA Institute. He is a Fellow of the Fields Institute, Toronto, and a Distinguished Fellow of the Zuse Institute Berlin. He had previously held a faculty position at the Tokyo Institute of Technology where he received his PhD, and longterm visiting positions at Université Paris Saclay,  where he has held a Digiteo Chair in Combinatorics and Optimization, and Technion Israel Institute of Technology. His research focuses on the computational, combinatorial, and geometric aspects of linear optimization.

Speaker:  Antoine Deza

Time:  March 7^th, 10:45 – 11:30

Room:  Boardroom, DY103, Daoyuan Building