Nonlinear discrete optimization II

Thursday, November 20, 2008 - 10:30am - 11:15am
EE/CS 3-180
Shmuel Onn (Technion-Israel Institute of Technology)
We develop an algorithmic theory of nonlinear optimization over sets
of integer points presented by inequalities or by oracles. Using a
combination of geometric and algebraic methods, involving zonotopes,
Graver bases, multivariate polynomials and Frobenius numbers, we provide
polynomial-time algorithms for broad classes of nonlinear combinatorial
optimization problems and integer programs in variable dimension.
I will overview this work, joint with many colleagues over the last few
years, and discuss some of its many applications in statistics and
operations research, including privacy in statistical databases,
experimental design, nonlinear transportation, multicommodity flows,
error-correcting codes, matroids and general independence systems.
MSC Code: