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)