New Results in Integer and Lattice Programming

An integer program (IP) is a problem of the form $\min \{f(x) : \, Ax = b, \ l \leq x \leq u, \ x \in \Z^n\}$, where $A \in \Z^{m \times n}$, $b \in \Z^m$, $l,u \in \Z^n$, and $f: \Z^n \rightarrow \Z$ is a separable convex objective function. The problem of finding an optimal solution for an integer program is known as integer programming. Integer programming is NP-hard in general, though several algorithms exist: Lenstra provided an algorithm that is polynomial if the dimension $n$ is fixed. For variable dimension, the best known algorithm depends linearly on $n$, and exponentially on the number of equalities as well as the largest absolute value of an entry in the matrix $A$.

The first part of this thesis considers integer programming for variable dimensions and sparse matrices. We measure the sparsity of a matrix by the tree-depth of the dual graph of $A$. A typical example for these integer programs are $N$-fold IPs, used for scheduling and social choice problems. We obtain the currently fastest fixed-parameter tractable algorithm with parameters tree-depth and the largest absolute value of the entries in $A$. The running time we achieve is near-linear in the dimension. With a slightly worse running time, we are able to show that $N$-fold integer programs of constant block size can be solved in strongly polynomial time. Assuming the exponential time hypothesis, we complement these results with a lower bound on the parameter dependency that almost matches the parameter dependency of the running time. As a consequence, we provide the currently strongest lower bound for $N$-fold integer programs.

Another problem closely related to integer programming is the closest vector problem. A lattice is a discrete additive subgroup of $\R^n$. The closest vector problem (CVP) asks for a lattice point closest to a given target vector. An important tool for solving the closest vector problem is the Voronoi cell $\vc$ of a lattice $\Lambda \subseteq \R^n$, which is the set of all points for which $0$ is a closest lattice point. It is a polytope whose facets are induced by a set of lattice vectors, the Voronoi relevant vectors. A generic lattice has exponentially many Voronoi relevant vectors, leading to exponential space for certain CVP algorithms.

In the second part of this thesis, we introduce the notion of a $c$-compact lattice basis $B \in \R^{n \times n}$ that facilitates to represent the Voronoi relevant vectors with coefficients bounded by $c$. Such a basis allows to reduce the space requirement of Micciancio's & Voulgaris' algorithm for the closest vector problem from exponential to polynomial, while the running time becomes exponential in $c$. We show that for every lattice an $n^2$-compact basis exists, but there are lattices for which we cannot choose $c \in o (n)$. If the Voronoi cell is a zonotope, we can choose $c=1$, providing a single-exponential time and polynomial space algorithm for CVP, assuming a $1$-compact basis is known.

Deciding whether a given lattice has a certain structure that helps to solve the closest vector problem more efficiently is a reappearing and non-trivial problem. The third part of this thesis is concerned with the specific structure of having an orthonormal basis. We show that this problem belongs to NP $\cap$ co-NP. Moreover, it can be reduced to solving a single closest vector problem. We also show that if a separation oracle for the Voronoi cell is provided, CVP is solvable in polynomial time.