Technion, IEM faculty - Operations Research seminar Speaker: Lyubov Romanchuk Title: Graver Bases Methods in Integer Programming Date: 24/01/2011 Time: 12:30 Place: Bloomfield-527 Abstract: <http://ie.technion.ac.il/seminar_files/1294650032_Lyuba_seminar.doc> Or see below: Graver Bases Methods in Integer Programming N-fold integer programming is a fundamental problem with a variety of natural applications in operations research and statistics. Moreover, it is universal and provides a new, variable-dimension, parametrization of all of integer programming. We use Graver bases methods to establish an iterative algorithm that solves this problem in polynomial time. Using it, we also propose a simple Graver approximation hierarchy, parameterized by degree, for nonlinear integer programming in general and optimization over multiway tables in particular, which makes use of quickly constructible approximations of the true Graver basis. We demonstrate this scheme for approximating the (universal) integer three-way table feasibility problem. This is the thesis work for M.Sc. in Operation Research under the supervision of Shmuel Onn. --------------------------------------------------------- Technion Math. Net (TECHMATH) Editor: Michael Cwikel <techm@math.technion.ac.il> Announcement from: <levinas@techunix.technion.ac.il>