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:
“The shortest route is not the most direct one, but rather the one where the most favorable winds swell our sails:Mthat is the lesson that seafarers teach. Not to abide by this lesson is to be obstinate: here, firmness of character is tainted with stupidity.”
—Friedrich Nietzsche (1844–1900)
“The basis of good manners is self-reliance. Necessity is the law of all who are not self-possessed.”
—Ralph Waldo Emerson (1803–1882)
“I tell you, sir, the only safeguard of order and discipline in the modern world is a standardized worker with interchangeable parts. That would solve the entire problem of management.”
—Jean Giraudoux (1882–1944)