pipette
ENEnglish

Integer Programing: An Algorithm with Exponent Linear in the Dimension

Lin Chen, Yuchen Mao, Guochuan Zhang

Preprint

En palabras de los autores

We study integer programs in standard form , where and all entries of are integers. Let be an upper bound on the absolute values of the entries of . We give a deterministic algorithm running in time \[ \operatorname{poly}(L_{\rm in})+ f(d) N^{O(d)}\bigl(1+\log(c_{\max}+1)\bigr)^{O(1)}, \] where bounds the absolute values of the costs and is the input length. Prior to our work, the best known running time was [Eisenbrand & Weismantel'20], and it has been a fundamental open problem whether the exponent can be improved to one linear in . We answer this question affirmatively.

Resultado principalEl resumen no menciona limitaciones.

Apareció: martes, 20 de octubre. arXiv. Preprint, todavía sin revisión por pares.