betaFeedback

WorksComputer Science

Bounded Integer Programming in Almost N2dN^{2d} Time

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}, all entries of b,c,l,u\mathbf{b},\mathbf{c},\mathbf{l},\mathbf{u} are integers, and every variable bound is finite. Let NN be an upper bound on the absolute values of the entries of AA, and cmax⁡c_{\max} one on the absolute values of the costs. For every fixed dd and every fixed ε>0\varepsilon>0 we give a deterministic algorithm running in time TLP+Od(n)+Od,ε(N2d+εlog⁡2(cmax⁡+2)), T_{\textrm LP}+O_d(n)+O_{d,\varepsilon}\bigl(N^{2d+\varepsilon}\log^2(c_{\max}+2)\bigr), where TLPT_{\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 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, with the exponent 2d+ε2d+\varepsilon.

Paper details

vlnc:W_xcmwcybj
Version
v2 · latest
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…