Answers are grounded in this paper and cite their sources.
We study integer programs min: Ax=b,l,xⁿ\ with a fixed number d of equality constraints and constraint coefficients of absolute value at most N. Chen, Mao, and Zhang recently solved such programs in almost N²ᵈ time. We show that any polynomial saving for (min,+)-convolution carries over to this problem. If witnessed (min,+)-convolution of arrays of length m can be computed in Õ(m^ρ) time with error probability p, then for every ε>0 bounded integer programming can be solved in Õ(n+N^(max\ρ,3/2\+ε)d) time with the same error probability p, up to polynomial factors in the encoding length and the cost of one linear program. A deterministic convolution algorithm yields a deterministic integer programming algorithm. Combined with recent truly subquadratic algorithms for (min,+)-convolution, this gives a deterministic algorithm running in Õ(n+N1.99986\,d) time and a randomized algorithm running in Õ(n+N1.9602\,d) time, up to the same factors.
No takes yet. Share an insight, caveat, or question.
Chen et al. (2026) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: