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

• 成果类型: Article; Early Access
• 署名作者: Hunkenschroder, Christoph; Koutecky, Martin; Levin, Asaf; Vu, Tung Anh
• 署名单位: Technical University of Berlin; Technion Israel Institute of Technology; Charles University Prague
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610; 1436-4646
• DOI: 10.1007/s10107-026-02341-5
• 发表日期: 2026-03-18
• 关键词: integer programming; parameterized complexity; Graver basis; Treedepth; n-fold; Tree-fold; 2-stage stochastic; Multi-stage stochastic; LINEAR TIME ALGORITHM; optimization; THEOREMS

摘要

We study the general integer programming (IP) problem of optimizing a separable convex function over the integer points of a polytope: min{ f (x) | Ax = b, 1 <= x <= u, x is an element of 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 IIAIIcand small primal or dual treedepth td(P) (A) or 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 (nonlinear) 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-1 ||(infinity), where l, u are the vectors of lower and upper bounds. Our first result is that with parameters tdP (A) and ||A||(infinity), this lower bound can be matched (up to dependency on the parameters). Second, with parameters td(D)(A) and ||A||(infinity), the situation is more involved, and we design an algorithm with time complexity g(td(D)(A), ||A||(infinity))n log(n) log ||u-1 ||(infinity) where 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.