The INI has a new website!

This is a legacy webpage. Please visit the new site to ensure you are seeing up to date information.

Skip to content



Integer quadratic minimization over polyhedra in dimension two

Weismantel, R (ETH Zürich)
Friday 19 July 2013, 12:00-12:30

Seminar Room 1, Newton Institute


This talk deals with algorithms and complexity results about the minimization of convex functions over integer points in convex regions. 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. We discuss 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 optimal value. We also show how to prove that such proximity results are best possible up to a polynomial factor.


[pdf ]


The video for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.

Back to top ∧