Integer quadratic programming in the plane

Abstract

We show that the problem of minimizing a quadratic polynomial with integer coefficients over the integer points in a general two-dimensional rational polyhedron is solvable in time bounded by a polynomial in the input size. Copyright © 2014 by the Society for Industrial and Applied Mathematics.