Abstract
In the talk I will present a polynomial time algorithm for solving the closest vector problem in the special class of lattices whose Voronoi cells are projection of cubes (zonotopes). Examples of this class of lattices include lattices of Voronoi's first kind and tensor products of root lattices of type A. The combinatorial structure of this class of lattices can be described by regular matroids (totally unimodular matrices). The main observation is that the generalization of the minimum mean cycling canceling method of Karzanov and McCormick can be applied here. This is joint work with Tom McCormick, Britta Peis, and Robert Scheidweiler.