The Quadratic Graver Cone, Quadratic Integer Minimization, and Extensions

Consider the general nonlinear integer minimization problem in standard form,
, (1) with with , and .

It is well known to be NP-hard already for linear functions. However, recently it was shown that, if the Graver basis G(A) of A is given as part of the input, then the problem can be solved in polynomial time for the following classes of functions. First, in [1], for composite concave functions , with concave, and d fixed. Second, in [3], for separable convex functions with each fi univariate convex, and in particular for linear functions . While the Graver basis is a complex object, it can be computed in polynomial time from A for many natural and useful classes of matrices as demonstrated in [1, 3]. Moreover, the results of [2] imply that there is a parameterized scheme that enables to construct increasingly better approximations of the Graver basis of any matrix A and obtain increasingly better approximations to problem (1), see [4] for details.

In this article we continue this line of investigation and consider problem (1) for quadratic functions with , , and . We also discuss extensions to multivariate polynomial functions of arbitrary degree.

We begin by noting that problem (1) remains NP-hard even if the Graver basis is part of the input and even if the objective function is quadratic convex of rank 1.

By: Jon Lee; Shmuel Onn; Lyubov Romanchuk; Robert Weismantel

Published in: RC24999 in 2010


This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.


Questions about this service can be mailed to .