arXiv:2610.25955 · v2

Bounded Integer Programming in Almost $N^{2d}$ Time

首次提交 2026-10-19 15:47

版本更新 2026-11-11 00:19

雷达观测 2026-11-11 13:07

摘要

We study integer programs in standard form $\min\{\mathbf{c}^{\mathsf T}\mathbf{x}:A\mathbf{x}=\mathbf{b},\mathbf{l}\leq\mathbf{x}\leq\mathbf{u},\ \mathbf{x}\in\mathbb{Z}^n\}$, where $A\in\mathbb{Z}^{d\times n}$, all entries of $\mathbf{b},\mathbf{c},\mathbf{l},\mathbf{u}$ are integers, and every variable bound is finite. Let $N$ be an upper bound on the absolute values of the entries of $A$, and $c_{\max}$ one on the absolute values of the costs. For every fixed $d$ and every fixed $\varepsilon>0$ we give a deterministic algorithm running in time \[ T_{\textrm LP}+O_d(n)+O_{d,\varepsilon}\bigl(N^{2d+\varepsilon}\log^2(c_{\max}+2)\bigr), \] where $T_{\textrm LP}$ is the time to solve one linear programming relaxation exactly. Prior to our work, the best known running time for bounded variables was $N^{O(d^2)}$ [Eisenbrand \& Weismantel'20], and it has been a fundamental open problem whether the exponent $O(d^2)$ can be improved to one linear in $d$. We answer this question affirmatively, with the exponent $2d+\varepsilon$.