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:
“Cultivated labor drives out brute labor. An infinite number of shrewd men, in infinite years, have arrived at certain best and shortest ways of doing, and this accumulated skill in arts, cultures, harvestings, curings, manufactures, navigations, exchanges, constitutes the worth of our world to-day.”
—Ralph Waldo Emerson (1803–1882)
“Independence I have long considered as the grand blessing of life, the basis of every virtue; and independence I will ever secure by contracting my wants, though I were to live on a barren heath.”
—Mary Wollstonecraft (1759–1797)
“The problem for the King is just how strict
The lack of liberty, the squeeze of the law
And discipline should be in school and state....”
—Robert Frost (1874–1963)