(Near)-Optimal algorithms for sparse separable convex integer programs

We study the general integer programming (IP) problem of optimizing a separable convex function over the integer points of a polytope: min (x) Ax= 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 log 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