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 answer is doing.”
—English proverb, collected in George Herbert, Jacula Prudentum (1651)
“The basis of successful relief in national distress is to mobilize and organize the infinite number of agencies of self help in the community. That has been the American way.”
—Herbert Hoover (1874–1964)
“The problem is simply this: no one can feel like CEO of his or her life in the presence of the people who toilet trained her and spanked him when he was naughty. We may have become Masters of the Universe, accustomed to giving life and taking it away, casually ordering people into battle or out of their jobs . . . and yet we may still dirty our diapers at the sound of our mommy’s whimper or our daddy’s growl.”
—Frank Pittman (20th century)