Shortest Basis Problem
Many problems become easier if the input basis consists of short vectors. An algorithm that solves the Shortest Basis Problem (SBP) must, given a lattice basis, output an equivalent basis such that the length of the longest vector in is as short as possible.
The approximation version problem consist of finding a basis whose longest vector is at most times longer than the longest vector in the shortest basis.
Read more about this topic: Lattice Problem
Famous quotes containing the words shortest, basis and/or problem:
“I have simplified my politics into an utter detestation of all existing governments; and, as it is the shortest and most agreeable and summary feeling imaginable, the first moment of an universal republic would convert me into an advocate for single and uncontradicted despotism. The fact is, riches are power, and poverty is slavery all over the earth, and one sort of establishment is no better, nor worse, for a people than another.”
—George Gordon Noel Byron (1788–1824)
“The basis of shame is not some personal mistake of ours, but the ignominy, the humiliation we feel that we must be what we are without any choice in the matter, and that this humiliation is seen by everyone.”
—Milan Kundera (b. 1929)
“War is not a life: it is a situation,
One which may neither be ignored nor accepted,
A problem to be met with ambush and stratagem,
Enveloped or scattered.”
—T.S. (Thomas Stearns)