Convex Integer Optimization and Universality of Multiway Polytopes
Shmuel Onn
Technion - Israel Institute of Technology
I'll start with two contrasting statements on multiway polytopes.
The Universality Theorem asserts that any rational polytope is
a short 3-way polytope and hence any linear and integer program
is one over short 3-way tables. The Optimization Theorem asserts
that convex (and in particular linear) integer optimization over
long d-way tables of any dimension d is polynomial time solvable.
I will then outline our more general recent theory establishing
the polynomial time solvability of convex integer optimization
over any n-fold system, implying the above Optimization Theorem.