← 研踪 PaperTrailarXiv:2611.24386 · v1
Even Faster Algorithms for Bounded Integer Programming
首次提交 2026-11-18 21:16
版本更新 2026-11-18 21:16
雷达观测 2026-11-19 15:04
摘要
We study integer programs with a fixed number of equality constraints and constraint coefficients of absolute value at most . Chen, Mao, and Zhang recently solved such programs in almost time. We show that any polynomial saving for -convolution carries over to this problem. If witnessed -convolution of arrays of length can be computed in time with error probability , then for every bounded integer programming can be solved in time with the same error probability , 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 -convolution, this gives a deterministic algorithm running in time and a randomized algorithm running in time, up to the same factors.
观测到的版本
相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-18 21:16 · 最新观测版本
Even Faster Algorithms for Bounded Integer Programming
We study integer programs with a fixed number of equality constraints and constraint coefficients of absolute value at most . Chen, Mao, and Zhang recently solved such programs in almost time. We show that any polynomial saving for -convolution carries over to this problem. If witnessed -convolution of arrays of length can be computed in time with error probability , then for every bounded integer programming can be solved in time with the same error probability , 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 -convolution, this gives a deterministic algorithm running in time and a randomized algorithm running in time, up to the same factors.
查看此版本解读 →查看此版本原文 ↗