Finding an Integral vector in an Unknown Polyhedral Cone

Abstract

We present an algorithm to find an integral vector in the polyhedral cone $\Gamma =\{X|\text{A}X\le \text{0}\}$, without assuming the explicit knowledge of $\text{A}$. About the polyhedral cone, $\Gamma$, it is only given that, (i) the elements of \textbf{A} are in $\{-d,-d+1,\dot{.}.,0,\dot{.}.,d-1,d\}$, $d\in \mathbb{N}$, and, (ii) $Y=[y(1),y(2),\dot{.}.,y(n)]$ is a non-zero integral solution to $\Gamma$. The proposed algorithm finds a non-zero integral vector in $\Gamma$ such that its maximum element is less than $(2d{)}^{2^{n-1}-1}/2^{n-1}$.

References in corpus (1)

• Lectures on 0/1-polytopes