No label defined (Q3783556)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 4047093
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 4047093

      Statements

      1986
      0 references
      algorithmic complexity
      0 references
      separation problem
      0 references
      separation oracle
      0 references
      perfect matching lattices
      0 references
      0 references
      [For the entire collection see Zbl 0592.00028.] The separation problem for a point lattice L of points of \({\mathbb{R}}^ n\) is defined as follows: input to the problem is a vector x; its output is either ``x\(\in L''\) or a vector \(c\in L^*\) such that \(c^ Tx\not\in {\mathbb{Z}}\). \(L^*\) denotes the dual lattice. A separation oracle is an oracle solving the separation problem. A polynomiality guarantee for an oracle is an integer p such that for every input x the corresponding output c satisfies \(<c>\leq <x>^ p\). \(<c>\) denotes the size of c. A rationality guarantee is an integer t such that the oracle rejects every vector in which any entry has denominator larger than t and offers a separation otherwise. The main result is the following theorem: If L is a lattice given by a separation oracle with polynomiality guarantee p and rationality guarantee t, then a basis for L can be computed in time polynomial in p and \(<t>\). Some results, conjectures and problems about perfect matching lattices are given.
      0 references

      Identifiers