(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 \{f(\vec{x}) \mid A\vec{x} = \vec{b}, \, \vec{l} \leq \vec{x} \leq \vec{u}, \, \vec{x} \in \mathbb{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\|_\infty\) and small primal or dual treedepth \(\mathrm{td}_P(A)\) or \(\mathrm{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 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 \|\vec{u}-\vec{l}\|_\infty\), where \(\vec{l}, \vec{u}\) are the vectors of lower and upper bounds. Our first result is that with parameters \(\mathrm{td}_P(A)\) and \(\|A\|_\infty\), this lower bound can be matched (up to dependency on the parameters). Second, with parameters \(\mathrm{td}_D(A)\) and \(\|A\|_\infty\), the situation is more involved, and we design an algorithm with complexity \(g(k) n \log n \log \|\vec{u}-\vec{l}\|_\infty\). We conjecture that a stronger lower bound is possible in this regime, and our algorithm is in fact optimal.

Our algorithms combine ideas from scaling, proximity, and sensitivity of integer programs, together with a new dynamic data structure allowing fast sparse updates.

This is joint work with Christoph Hunkenschröder, Martin Koutecký, and Asaf Levin.