Universität zu Köln

McCormick, S. Thomas, Peis, Britta, Scheidweiler, Robert and Vallentin, Frank (2021). A POLYNOMIAL TIME ALGORITHM FOR SOLVING THE CLOSEST VECTOR PROBLEM IN ZONOTOPAL LATTICES\ast. SIAM Discret. Math., 35 (4). S. 2345 - 2357. PHILADELPHIA: SIAM PUBLICATIONS. ISSN 1095-7146

Full text not available from this repository.

Abstract

In this note we give a polynomial time algorithm for solving the closest vector problem in the class of zonotopal lattices. The Voronoi cell of a zonotopal lattice is a zonotope, i.e., a projection of a regular cube. Examples of zonotopal lattices include lattices of Voronoi's first kind and tensor products of root lattices of type A. The combinatorial structure of zonotopal lattices can be described by regular matroids/totally unimodular matrices. We observe that a linear algebra version of the minimum mean cycle canceling method can be applied for efficiently solving the closest vector problem in a zonotopal lattice if the lattice is given as the integral kernel of a totally unimodular matrix.

Item Type:	Journal Article
Creators:	Creators Email ORCID ORCID Put Code McCormick, S. Thomas UNSPECIFIED UNSPECIFIED UNSPECIFIED Peis, Britta UNSPECIFIED UNSPECIFIED UNSPECIFIED Scheidweiler, Robert UNSPECIFIED UNSPECIFIED UNSPECIFIED Vallentin, Frank UNSPECIFIED UNSPECIFIED UNSPECIFIED
URN:	urn:nbn:de:hbz:38-578422
DOI:	10.1137/20M1382258
Journal or Publication Title:	SIAM Discret. Math.
Volume:	35
Number:	4
Page Range:	S. 2345 - 2357
Date:	2021
Publisher:	SIAM PUBLICATIONS
Place of Publication:	PHILADELPHIA
ISSN:	1095-7146
Language:	English
Faculty:	Unspecified
Divisions:	Unspecified
Subjects:	no entry
Uncontrolled Keywords:	Keywords Language SPACE; OPTIMIZATION Multiple languages Mathematics, Applied Multiple languages
URI:	http://kups.ub.uni-koeln.de/id/eprint/57842