Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
An integer program (IP) is a problem of the form , where , , , and 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 is fixed. For variable dimension, the best known algorithm depends linearly on , and exponentially on the number of equalities as well as the largest absolute value of an entry in the matrix .
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 typical example for these integer programs are -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 . The running time we achieve is near-linear in the dimension. With a slightly worse running time, we are able to show that -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 -fold integer programs.
Another problem closely related to integer programming is the closest vector problem. A lattice is a discrete additive subgroup of . 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 of a lattice , which is the set of all points for which 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 -compact lattice basis that facilitates to represent the Voronoi relevant vectors with coefficients bounded by . 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 . We show that for every lattice an -compact basis exists, but there are lattices for which we cannot choose . If the Voronoi cell is a zonotope, we can choose , providing a single-exponential time and polynomial space algorithm for CVP, assuming a -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 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.
Daniel Kressner, Alice Cortinovis