On the Structure of Reduced Kernel Lattice Bases

Karen Aardal, Frederik von Heymann

Research output: Contribution to journalArticleScientificpeer-review

1 Citation (Scopus)

Abstract

Lattice-based reformulation techniques have been used successfully both theoretically and computationally. One such refor-mulation is obtained from the kernel lattice associated with an input matrix. Some of the hard instances in the literature thathave been successfully tackled by lattice-based techniques have randomly generated input. Since the considered instances arevery hard even in low dimension, less experience is available for larger instances. Recently, we have studied larger instancesand observed that the LLL-reduced basis of the kernel lattice has a specific sparse structure. In particular, this translates intoa map in which some of the original variables get a “rich”’ translation into a new variable space, whereas some variables areonly substituted in the new space. If an original variable is important in the sense of branching or cutting planes, this variableshould be translated in a nontrivial way. In this paper we partially explain, through a probabilistic analysis, the obtainedstructure of the LLL-reduced basis in the case that the input matrix consists of one row. The key ingredient is a bound onthe probability that the LLL-algorithm will interchange two subsequent basis vectors
Original languageEnglish
Pages (from-to)823-840
Number of pages18
JournalMathematics of Operations Research
Volume39
Issue number3
DOIs
Publication statusPublished - 2014

Keywords

  • lattice reformulation
  • lattice bases
  • LLL-algorithm
  • probabilistic analysis

Fingerprint Dive into the research topics of 'On the Structure of Reduced Kernel Lattice Bases'. Together they form a unique fingerprint.

  • Cite this