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.
EPFL_TH7727.pdf
openaccess
1.42 MB
Adobe PDF
4414774dd2a9c6e8df1009d406abba3b