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)
“Socialism proposes no adequate substitute for the motive of enlightened selfishness that to-day is at the basis of all human labor and effort, enterprise and new activity.”
—William Howard Taft (1857–1930)
“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)