Approximate integer programming is the following: For a convex body $K\subseteq {\mathbb{R}}^{n}$ , either determine whether $K\cap {\mathbb{Z}}^{n}$ is
empty, or find an integer point in the convex body scaled by $2$ from its
center of gravity $c$ . Approximate integer programming can be solved in time
${2}^{O(n)}$ while the fastest known methods for exact integer programming run in
time ${2}^{O(n)}\cdot {n}^{n}$ . So far, there are no efficient methods for integer
programming known that are based on approximate integer programming. Our main
contribution are two such methods, each yielding novel complexity results.
First, we show that an integer point ${x}^{\ast}\in (K\cap {\mathbb{Z}}^{n})$ can be
found in time ${2}^{O(n)}$ , provided that the remainders of each component ${x}_{i}^{\ast}\phantom{\rule{0.667em}{0ex}}\mathrm{mod}{\textstyle \phantom{\rule{0.167em}{0ex}}}{\textstyle \phantom{\rule{0.167em}{0ex}}}\ell $ for some arbitrarily fixed $\ell \ge 5(n+1)$ of ${x}^{\ast}$ are given.
The algorithm is based on a cutting-plane technique, iteratively halving the
volume of the feasible set. The cutting planes are determined via approximate
integer programming. Enumeration of the possible remainders gives a
${2}^{O(n)}{n}^{n}$ algorithm for general integer programming. This matches the
current best bound of an algorithm by Dadush (2012) that is considerably more
involved. Our algorithm also relies on a new asymmetric approximate
Carath\'eodory theorem that might be of interest on its own.
Our second method concerns integer programming problems in equation-standard
form $Ax=b,0\le x\le u,{\textstyle \phantom{\rule{0.167em}{0ex}}}x\in {\mathbb{Z}}^{n}$ . Such a problem can be
reduced to the solution of $\prod _{i}O(\mathrm{log}{u}_{i}+1)$ approximate integer
programming problems. This implies, for example that knapsack or subset-sum
problems with polynomial variable range $0\le {x}_{i}\le p(n)$ can be solved in
time $(\mathrm{log}n{)}^{O(n)}$ . For these problems, the best running time so far was
${n}^{n}\cdot {2}^{O(n)}$ .

PREPRINT

# From approximate to exact integer programming

Daniel Dadush, Friedrich Eisenbrand, Thomas Rothvoss

Submitted on 7 November 2022

## Abstract

## Preprint

Subjects: Mathematics - Optimization and Control; Computer Science - Computational Complexity; Computer Science - Discrete Mathematics; Computer Science - Data Structures and Algorithms; Mathematics - Combinatorics; 15A, 52B, 52C, 68Q, 68R, 68W, 90B, 90C; F.2.2; G.1.6