日時： 2017年7月11日(火) 17:00～18:00
場所： 東京大学工学部 14号館 5階 534号室
http://www.u-tokyo.ac.jp/campusmap/cam01_04_15_j.html
講演者： S. Thomas McCormick
講演題目: 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^m. 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 an n by m 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(m^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. The new
algorithm is more general and often faster than a CVP algorithm for
co-circulation matrices by McKilliam, Grant, and Clarkson that runs in
O(n^4) time.
S. Thomas McCormick (UBC)
Britta Peis, Robert Scheidweiler (RWTH Aachen)
Frank Vallentin (Cologne)