Worst-case constructions for linear optimization
Antoine Deza, McMaster University


Worst-case constructions have helped providing a deeper understanding of how
the structural properties of the input affect the computational
performance of linear optimization. Recent examples include the construction
of Allamigeon et al. for which the self-concordant barrier 
interior point method performs an exponential number of iterations, and thus
is not strongly polynomial. In a similar spirit,
recent lower bounds on the number of simplex pivots required in
the worst-case to perform linear optimization over a lattice polytope will
be presented, as well as the first worst-case instances for
geometric scaling methods that solve integer optimization problems by primal
augmentation steps. 

This talk is based on joint work with Shmuel
Onn, George Manoussakis, Sebastian Pokutta, and Lionel Pournin