Finding an Integral vector in an Unknown Polyhedral Cone
classification
🧮 math.OC
keywords
gammaintegraltextbfconepolyhedralvectoralgorithmnon-zero
read the original abstract
We present an algorithm to find an integral vector in the polyhedral cone $\Gamma=\{X | \textbf{A}X \leq \textbf{0}\}$, without assuming the explicit knowledge of $\textbf{A}$. About the polyhedral cone, $\Gamma$, it is only given that, (i) the elements of \textbf{A} are in $\{-d,-d+1,\...,0,\...,d-1,d\}$, $d \in \mathbb{N}$, and, (ii) $Y=[y(1),y(2),\...,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}}$.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.