I will overview our recent algorithmic theory which uses Graver bases to solve linear and nonlinear integer programming problems in variable dimension in polynomial time. I will demonstrate the power of this theory by providing polynomial time solutions of (nonlinear) multiway statistical table problems, multicommodity flows and stochastic integer programming, show that this theory is universal and provides a new parametrization of all of integer programming, and indicate a simple approximation hierarchy suggested by this framework. The talk will draw from my new monograph (Nonlinear Discrete Optimization, Zurich Lectures in Advanced Mathematics, European Mathematical Society, September 2010).
Copyright. All Rights Reserved.