- Robert Weismantel, ETH Zürich, Switzerland
"Mixed Integer Convex Optimization"
This talk deals with algorithms and complexity results
about the minimization of convex functions over mixed integer points in
This topic is quite novel and today only few
non-trivial algorithmic methods exist that can cope with problems of
this generality. We survey current state of art, both when the
number of integer
variables is constant and variable.
results about the speed of convergence of oracle algorithms that
iteratively solve special integer subproblems with a constant
approximation factor. Despite the generality of the underlying
setting we show how to detect efficiently w.r.t. our oracle assumptions
feasible solutions whose objective function value is close to the
We also show how to prove that such proximity results are best possible up to a polynomial factor.