(Near)-Optimal Algorithms for Sparse Separable Convex Integer Programs

Christoph Hunkenschröder, Martin Koutecký, Asaf Levin +1

We study the general integer programming (IP) problem of optimizing a separable convex function over the integer points of a polytope: $\min \{f(\mathbf{x}) \mid A\mathbf{x} = \mat…