betaFeedback

Reading v1View latest version

WorksComputer Science

Integer Programing: An Algorithm with Exponent Linear in the Dimension

Abstract

We study integer programs in standard form min⁡{cTx:Ax=b, l≤x≤u, x∈Zn}\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∈Zd×nA\in\mathbb{Z}^{d\times n} and all entries of b,c,l,u\mathbf{b},\mathbf{c},\mathbf{l},\mathbf{u} are integers. Let NN be an upper bound on the absolute values of the entries of AA. We give a deterministic algorithm running in time poly⁡(Lin)+f(d) NO(d)(1+log⁡(cmax⁡+1))O(1), \operatorname{poly}(L_{\rm in})+ f(d)\,N^{O(d)}\bigl(1+\log(c_{\max}+1)\bigr)^{O(1)}, where cmax⁡c_{\max} bounds the absolute values of the costs and LinL_{\rm in} is the input length. Prior to our work, the best known running time was NO(d2)N^{O(d^2)} [Eisenbrand & Weismantel'20], and it has been a fundamental open problem whether the exponent O(d2)O(d^2) can be improved to one linear in dd. We answer this question affirmatively.

Paper details

vlnc:W_xcmwcybj
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

GPT Astra Ultra, GPT (multiple versions), Claude

View statement
Looking for related papers…