Curvature batching gives single-exponential integer quadratic programming
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866918430132666368 |
|---|---|
| author | Ari, Cinar Hildebrand, Robert |
| author_facet | Ari, Cinar Hildebrand, Robert |
| contents | Integer Quadratic Programming (IQP), $\min\{x^T Q x + c^T x : Ax \le b,\, x\in\Z^n\}$, is a fundamental problem in combinatorial optimization. While the convex and concave special cases admit polynomial-time algorithms for fixed~$n$, the general indefinite case is considerably harder: it was only recently shown to lie in NP, and the FPT algorithm, due to Lokshtanov, establishes fixed-parameter tractability parameterized by $n$ and the largest coefficient~$L$ without giving an explicit running time.
We give the first single-exponential algorithm for IQP, solving it in time $
\bigl(n\,L^n_A\,Δ(A)\,L_Q\bigr)^{O(n)}\cdot\mathrm{poly}(φ), $ which is $(nL)^{O(n^2)}\cdot\mathrm{poly}(φ)$ in general using the same parameterization. We achieve improvements for structured cases like total unimodularity and further state explicit complexity results for a number of FPT algorithms and optimization problems.
The single-exponential bound is achieved via curvature batching: we classify kernel directions by the sign of their quadratic curvature and observe that when no negative-curvature direction exists, all gradient constraints can be imposed simultaneously in a single batch. This replaces the chain of determinant squarings inherent in sequential branching with a single polynomial inflation, after which the remaining problem is an ILP.
As a secondary contribution, we give an explicit bound for concave integer minimization over a polytope $\{Ax \le b\} \cap \Z^n$ whose parametric complexity depends only on the constraint matrix~$A$ and is independent of the right-hand side~$b$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_04851 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Curvature batching gives single-exponential integer quadratic programming Ari, Cinar Hildebrand, Robert Optimization and Control Integer Quadratic Programming (IQP), $\min\{x^T Q x + c^T x : Ax \le b,\, x\in\Z^n\}$, is a fundamental problem in combinatorial optimization. While the convex and concave special cases admit polynomial-time algorithms for fixed~$n$, the general indefinite case is considerably harder: it was only recently shown to lie in NP, and the FPT algorithm, due to Lokshtanov, establishes fixed-parameter tractability parameterized by $n$ and the largest coefficient~$L$ without giving an explicit running time. We give the first single-exponential algorithm for IQP, solving it in time $ \bigl(n\,L^n_A\,Δ(A)\,L_Q\bigr)^{O(n)}\cdot\mathrm{poly}(φ), $ which is $(nL)^{O(n^2)}\cdot\mathrm{poly}(φ)$ in general using the same parameterization. We achieve improvements for structured cases like total unimodularity and further state explicit complexity results for a number of FPT algorithms and optimization problems. The single-exponential bound is achieved via curvature batching: we classify kernel directions by the sign of their quadratic curvature and observe that when no negative-curvature direction exists, all gradient constraints can be imposed simultaneously in a single batch. This replaces the chain of determinant squarings inherent in sequential branching with a single polynomial inflation, after which the remaining problem is an ILP. As a secondary contribution, we give an explicit bound for concave integer minimization over a polytope $\{Ax \le b\} \cap \Z^n$ whose parametric complexity depends only on the constraint matrix~$A$ and is independent of the right-hand side~$b$. |
| title | Curvature batching gives single-exponential integer quadratic programming |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2604.04851 |