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

  • Date: 04/18/2017
  • Time: 12:30
Lecturer(s):
S. Thomas McCormick, UBC
Location: 

University of British Columbia

Topic: 

Computing closest vectors in zonotopal lattices

Description: 

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)

Other Information: 

Location: ESB 4133 (PIMS Lounge)