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>