@misc{HenkWeismantel, author = {Henk, Martin and Weismantel, Robert}, title = {On Hilbert bases of polyhedral cones}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2230}, number = {SC-96-12}, abstract = {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.}, language = {en} } @misc{HenkWeismantel, author = {Henk, Martin and Weismantel, Robert}, title = {Test sets of the knapsack problem and simultaneous diophantine approximation}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2825}, number = {SC-97-13}, abstract = {This paper deals with the study of test sets of the knapsack problem and simultaneous diophantine approximation. The Graver test set of the knapsack problem can be derived from minimal integral solutions of linear diophantine equations. We present best possible inequalities that must be satisfied by all minimal integral solutions of a linear diophantine equation and prove that for the corresponding cone the integer analogue of Caratheodory's theorem applies when the numbers are divisible. We show that the elements of the minimal Hilbert basis of the dual cone of all minimal integral solutions of a linear diophantine equation yield best approximations of a rational vector ``from above''. A recursive algorithm for computing this Hilbert basis is discussed. We also outline an algorithm for determining a Hilbert basis of a family of cones associated with the knapsack problem.}, language = {en} } @misc{HenkWeismantel, author = {Henk, Martin and Weismantel, Robert}, title = {Hilbert bases of cones related to simultaneous Diophantine approximations and linear Diophantine equations}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2989}, number = {SC-97-29}, abstract = {This paper investigates properties of the minimal integral solutions of a linear diophantine equation. We present best possible inequalities that must be satisfied by these elements which improves on former results. We also show that the elements of the minimal Hilbert basis of the dual cone of all minimal integral solutions of a linear diophantine equation yield best approximations of a rational vector ``from above''. Relations between these cones are applied to the knapsack problem.}, language = {en} } @misc{BrunsGubeladzeHenketal., author = {Bruns, Winfried and Gubeladze, Joseph and Henk, Martin and Martin, Alexander and Weismantel, Robert}, title = {A counterexample to an integer analogue of Caratheodorys theorem}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3718}, number = {SC-98-28}, abstract = {For \$n\geq 6\$ we provide a counterexample to the conjecture that every integral vector of a \$n\$-dimensional integral polyhedral pointed cone \$C\$ can be written as a nonnegative integral combination of at most \$n\$ elements of the Hilbert basis of \$C\$. In fact, we show that in general at least \$\lfloor 7/6 \cdot n \rfloor\$ elements of the Hilbert basis are needed.}, language = {en} }