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)
“Knighterrantry is a most chuckleheaded trade, and it is tedious hard work, too, but I begin to see that there is money in it, after all, if you have luck. Not that I would ever engage in it, as a business, for I wouldn’t. No sound and legitimate business can be established on a basis of speculation. A successful whirl in the knighterrantry line—now what is it when you blow away the nonsense and come down to the cold facts? It’s just a corner in pork, that’s all.”
—Mark Twain [Samuel Langhorne Clemens] (1835–1910)
“My problem lies in reconciling my gross habits with my net income.”
—Errol Flynn (1909–1959)