Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $\vec v\in\mathbb Q^n$. Is there an efficient algorithm to compute the smallest (in the $\ell_\infty$ norm) nonzero vector $\vec w\in\mathbb Z^n$ such that $\vec v\cdot \vec w=0$? Equivalently, if we let $A$ be a matrix with columns consisting of a basis for the nullspace of $\vec v^T$, can we find the smallest element of $\mathbb Z^n$ in the image of $A$?

I would also be interested in approximation algorithms, which perhaps do not give the smallest such vector but the vector $\vec w'$ they give satisfies $\|\vec w'\|_\infty/\|\vec w\|_\infty < C$ for some $C$ which does not depend of $\vec v$ (but may depend on $n$). For example an algorithm which minimizes the $\ell_2$ norm would suffice.

share|improve this question

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.