pith. sign in

arxiv: 1002.0117 · v4 · pith:WH23BFCSnew · submitted 2010-01-31 · 🧮 math.OC

Finding an Integral vector in an Unknown Polyhedral Cone

classification 🧮 math.OC
keywords gammaintegraltextbfconepolyhedralvectoralgorithmnon-zero
0
0 comments X
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.