On Hilbert bases of polyhedral cones
Please always quote using this URN: urn:nbn:de:0297-zib-2230
- For a polyhedral cone $C=$ pos $\{a^1,\dots,a^m\}\subset R^d$, $a^i\in Z^d$, a subset of integral vectors $H(C)\subset C \cap Z^d$ is called a Hilbert basis of $C$ iff (i) each element of $C\cap Z^d$ can be written as a non-negative integer combination of elements of $H(C)$ and (ii) $H(C)$ has minimal cardinality with respect to all subsets of $C \cap Z^d$ for which (i) holds. We show that various problems related to Hilbert bases are hard in terms of computational complexity. However, if the dimension and the number of elements of the Hilbert basis are fixed, a Hilbert basis can always be computed in polynomial time. Furthermore we introduce a (practical) algorithm for computing the Hilbert basis of a polyhedral cone. The finiteness of this method is deduced from a result about the height of a Hilbert basis which, in particular, improves on former estimates.
Download full text files
Additional Services
| Author: | Martin Henk, Robert Weismantel |
|---|---|
| Document Type: | ZIB-Report |
| Date of first Publication: | 1996/04/02 |
| Series (Serial Number): | ZIB-Report (SC-96-12) |
| ZIB-Reportnumber: | SC-96-12 |
| Published in: | Appeared in: Results in Mathematics 32 (1997) 298-303 |
