论文标题
用于求解技术晶格中最接近的向量问题的多项式时间算法
A polynomial time algorithm for solving the closest vector problem in zonotopal lattices
论文作者
论文摘要
在本说明中，我们给出了一种多项式时间算法，用于求解分流晶格类中最接近的向量问题。地位晶格的Voronoi细胞是一个Zonotope，即常规立方体的投影。分子晶格的实例包括Voronoi的第一类的晶格和A型的根晶格的张量产品。可以通过常规的Matroid/完全单型矩阵来描述地位晶格的组合结构。我们观察到，如果将晶格作为完全单型矩阵的积分内核，则可以应用最小平均周期取消方法的线性代数版本，以有效地求解晶格中最接近的矢量问题。
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.
