## Scientific Computation and Applied & Industrial Mathematics: S. Thomas McCormick

- Date: 04/18/2017
- Time: 12:30

University of British Columbia

Computing closest vectors in zonotopal lattices

A lattice L is the set of vectors arising from integer linear combinations of given basis vectors in R^n. Given some vector x, the Closest Vector Problem (CVP) is to find a vector v in L of minimum l_2-norm distance to x. CVP is a fundamental problem for lattices with many applications, and it is in general NP Hard.

A zonotopal lattice is given as the set of integer points {v | Mv = 0} when M is a totally unimodular matrix. We show how to adapt the Cancel and Tighten algorithm of Karzanov and McCormick to solve CVP for zonotopal lattices in O(n^3) time via the Seymour decomposition of totally unimodular matrices. The algorithm uses the decomposition to reduce the problem to a series of subproblems that are piecewise linear convex circulation and co-circulation network flow problems.

by

Britta Peis, Robert Scheidweiler (RWTH Aachen)

S. Thomas McCormick (UBC Sauder)

Frank Vallentin (Cologne)

Location: ESB 4133 (PIMS Lounge)