Technion Computer Science Colloquium 15/03/2011 Time+Place : Tuesday 15/03/2011 14:30 room 337-8 Taub Bld. Speaker : Shmuel Onn Affiliation: IE&M, Technion Host : Johann Makowsky Title : The Graver Complexity of Integer Programming Abstract : 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). Short Biography: Shmuel Onn is a Professor of Operations Research at IE&M, Technion. He received his Ph.D. from Cornell University in 1992 and is a frequent visitor of the Mathematical Research Institutes at Berkeley, Banff, Oberwolfach, and ETH Zurich. He is a recipient of the 2010 INFORMS Computing Society Prize, 2009 IBM Faculty Award, 2005 Henry Taub Prize, and 2005 ORSIS Prize, and is author of the research monograph Nonlinear Discrete Optimization published by the European Mathematical Society in September 2010. Refreshments served from 14:15 on, Lecture starts at 14:30 ---------------------------------------------------------- Visit our home page- <http://www.cs.technion.ac.il/~colloq> Thu Feb 24 14:34:55 IST 2011 --------------------------------------------------------- Technion Math. Net (TECHMATH) Editor: Michael Cwikel <techm@math.technion.ac.il> Announcement from: Hadas Heier <heier@cs.technion.ac.il>