Clarification on FPTAS optimization in a paper

Question

In the abstract of this paper by Hildebrand, Weismantel & Zemmer it is stated that they provide an FPTAS for $$\min x'Qx$$ over a fixed dimension polyhedron when $Q$ has at most one negative or one positive eigenvalue.

Does it also provide FPTAS for $$\min_{(x_1,x_2,\dots,x_n,z)\in P\cap\mathbb Z^{n+1}}\quad \begin{bmatrix}x_1 & x_2 & \dots & x_n & z\end{bmatrix}Q\begin{bmatrix}x_1\\x_2\\\vdots\\x_n\\z\end{bmatrix}+\lambda z$$ where $\lambda\in\mathbb Z$ and $n$ are fixed and $Q$ has at most one negative or at most one positive eigenvalue?

---

Answer 1

Unfortunately, no. The form we use is very restrictive. The key is that the function $f(x)$ can be decomposed in a sign compatible way as $f(x) = g(x) h(x)$, where $g(x)$ is convex (or concave) and $h(x)$ is "sliceable". \emph{Sliceable} is a notion that we define that works with our approximation method. Most common sliceble functions are either products or sums of linear forms (sign compatible).
In the context of quadratic programming, the key example is:

$f(x,y,z) = x^2 + y^2 - z^2$.

Then $f$ can be decomposed as the product of $g(x,y,z) = \sqrt{x^2 + y^2} - |z|$ and $h(x,y,z) = \sqrt{x^2 + y^2} + |z|$. If we assume that $z \geq 0$, then $g$ is convex and $h$ is slicable.

The fact that $f = g*h$ allows us to get the approximation factor by minimizing $g$ on certain scaled boxes and then allowing the minimum of $h$ to be reasonably approximated due to its "slicability". Comparing solutions on all boxes returns the approximated solution.

Unfortunately, even adding linear terms as you propose above (typically) destroys this approximation technique. Unless there are some restrictions on the variables that allow the decomposition to still follow our rules.

Other approximations for polynomial integer programming are typically in terms of a f_max value and f_min value. See works of De Loera, Hemmecke, Koeppe, Weismantel and also of Del Pia.