# Lattice Reduction Problem: Minimizing the Longest Vector

Suppose we have a basis for an integer lattice formed by the vectors $\vec v_1, \vec v_2, \ldots,\vec v_n$. Then let $A$ be the augmented matrix $( \vec v_1| \space \vec v_2| \cdots |\space \vec v_n)$.

Here is my question: is there an algorithm which performs elementary column operations on $A$ such that $\max(\|\vec v_1\|_p, \|\vec v_2\|_p, \ldots, \|\vec v_n\|_p)$ is a minimum? The specific cases $p=1$, $p=2$, and $p=\infty$ are of particular interest to me.

Here are my thoughts for a brute force approach:

I could first apply the LLL algorithm to get my vectors within a reasonable distance of the origin. Once that is done, a $L_p$ unit $n$-sphere could be drawn centered at the origin with radius extended to the longest of the vectors. Every possible basis could then be compared with the original basis until the one with the minimized longest-vector is found. (I am not sure how to do this last part though).

EDIT:

It looks like the $p=\infty$ case can be reduced to a simpler problem, which is simply minimizing the largest element in the matrix. I have also found an article which looks promising in that it may have the answer for the $p=1$ case, but it is hardly legible to a simpleton like me.

-
 For $p = 2$, this is surely NP-hard, but if you insist, algorithms do exist that solve such problems. You could do an enumeration, and look for the $n$ shortest vectors (and some more if they are dependent). Several other methods exist, but all known methods are at least exponential in the dimension $n$. – TMM Dec 30 '12 at 2:25