Abstract We study the general integer programming (IP) problem of optimizing a separable convex function over the integer points of a polytope: \f ({ {x}) A {x}= {b}, \, {l} {x} {u}, \, {x} Zⁿ\} min f (x) ∣ A x = b, l ≤ x ≤ u, x ∈ Z n. The number of variables n is a variable part of the input, and we consider the regime where the constraint matrix A has small coefficients A _ ‖ A ‖ ∞ and small primal or dual treedepth {\, td\, }P (A) td P (A) or {\, td\, }D (A) td D (A), respectively. Equivalently, we consider block-structured matrices, in particular n -fold, tree-fold, 2-stage and multi-stage matrices. We ask about the possibility of near-linear time algorithms in the general case of (non-linear) separable convex functions. The techniques of previous works for the linear case are inherently limited to it; in fact, no strongly-polynomial algorithm may exist due to a simple unconditional information-theoretic lower bound of n {u}- {l} _ n log ‖ u - l ‖ ∞, where {l}, {u} l, u are the vectors of lower and upper bounds. Our first result is that with parameters {\, td\, }P (A) td P (A) and A _ ‖ A ‖ ∞, this lower bound can be matched (up to dependency on the parameters). Second, with parameters {\, td\, }D (A) td </mml: mr
Hunkenschröder et al. (Wed,) studied this question.