On simultaneous approximation in quadratic integer programming

It is shown how to replace the objective function of an integer quadratic programming problem by an integer objective function whose size is polynomially bounded by the number of variables and the size of the constraints, without changing the set of optimal solutions. The Frank and Tardos’ algorithm is used which in turn uses the simultaneous approximation algorithm of Lenstra et al. This preprocessing algorithm assures that the running time of any algorithm for solving integer quadratic programming problems can be made independent of the size of the objective function coefficients.