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 Gettysburg speech is at once the shortest and the most famous oration in American history. Put beside it, all the whoopings of the Websters, Sumners and Everetts seem gaudy and silly. It is eloquence brought to a pellucid and almost gem-like perfection—the highest emotion reduced to a few poetical phrases.”
—H.L. (Henry Lewis)
“The basis of our governments being the opinion of the people, the very first object should be to keep that right; and were it left to me to decide whether we should have a government without newspapers, or newspapers without a government, I should not hesitate a moment to prefer the latter.”
—Thomas Jefferson (1743–1826)
“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)