A counterexample to an integer analogue of Caratheodorys theorem
Please always quote using this URN: urn:nbn:de:0297-zib-3718
- 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.
Author: | Winfried Bruns, Joseph Gubeladze, Martin Henk, Alexander Martin, Robert Weismantel |
---|---|
Document Type: | ZIB-Report |
Tag: | Hilbert basis; Integral pointed cones; integral Carathéodory property |
MSC-Classification: | 90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C10 Integer programming |
Date of first Publication: | 1998/11/02 |
Series (Serial Number): | ZIB-Report (SC-98-28) |
ZIB-Reportnumber: | SC-98-28 |
Published in: | Appeared in: Journal für die Reine und Angewandte Mathematik 510, 1999, pp. 179-185 |