Mathematical Programming Программное обеспечение

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

Christoph Hunkenschröder, Martin Koutecký, Asaf Levin, Tung Anh Vu
Springer Nature · 2026-03-18 · DOI 10.1007/s10107-026-02341-5

Аннотация

Abstract We study the general integer programming (IP) problem of optimizing a separable convex function over the integer points of a polytope: $$\min \{f({\textbf {x}}) \mid A{\textbf {x}}= {\textbf {b}}, \, {\textbf {l}}\le {\textbf {x}}\le {\textbf {u}}, \, {\textbf {x}}\in \mathbb {Z}^n\}$$ 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 $$\Vert A\Vert _\infty $$ ‖ A ‖ ∞ and small primal or dual treedepth $${{\,\mathrm{\textrm{td}}\,}}_P(A)$$ td P ( A ) or $${{\,\mathrm{\textrm{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 \Vert {\textbf {u}}-{\textbf {l}}\Vert _\infty $$ n log ‖ u - l ‖ ∞ , where $${\textbf {l}}, {\textbf {u}}$$ l , u are the vectors of lower and upper bounds. Our first result is that with parameters $${{\,\mathrm{\textrm{td}}\,}}_P(A)$$ td P ( A ) and $$\Vert A\Vert _\infty $$ ‖ A ‖ ∞ , this lower bound can be matched (up to dependency on the parameters). Second, with parameters $${{\,\mathrm{\textrm{td}}\,}}_D(A)$$ td D ( A ) and $$\Vert A\Vert _\infty $$ ‖ A ‖ ∞ , the situation is more involved, and we design an algorithm with time complexity $$g({{\,\mathrm{\textrm{td}}\,}}_D(A), \Vert A\Vert _\infty ) n \log (n) \log \Vert {\textbf {u}}-{\textbf {l}}\Vert _\infty $$ g ( td D ( A ) , ‖ A ‖ ∞ ) n log ( n ) log ‖ u - l ‖ ∞ where $$g$$ g is some computable function. 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.

Читать у издателя →