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

  • Date: 04/18/2017
  • Time: 12:30
S. Thomas McCormick, UBC

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.

Britta Peis, Robert Scheidweiler (RWTH Aachen)
S. Thomas McCormick (UBC Sauder)
Frank Vallentin (Cologne)

Other Information: 

Location: ESB 4133 (PIMS Lounge)