  A classic result by Cook, Gerards, Schrijver, and Tardos provides an upper
bound of $n \Delta$ on the proximity of optimal solutions of an Integer Linear
Programming problem and its standard linear relaxation. In this bound, $n$ is
the number of variables and $\Delta$ denotes the maximum of the absolute values
of the subdeterminants of the constraint matrix. Hochbaum and Shanthikumar, and
Werman and Magagnosc showed that the same upper bound is valid if a more
general convex function is minimized, instead of a linear function. No
proximity result of this type is known when the objective function is
nonconvex. In fact, if we minimize a concave quadratic, no upper bound can be
given as a function of $n$ and $\Delta$. Our key observation is that, in this
setting, proximity phenomena still occur, but only if we consider also
approximate solutions instead of optimal solutions only. In our main result we
provide upper bounds on the distance between approximate (resp., optimal)
solutions to a Concave Integer Quadratic Programming problem and optimal
(resp., approximate) solutions of its continuous relaxation. Our bounds are
functions of $n, \Delta$, and a parameter $\epsilon$ that controls the quality
of the approximation. Furthermore, we discuss how far from optimal are our
proximity bounds.
