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.7819381952285767
0 references
0.7627907395362854
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