Carathéodory rank
Let [math]A=\{a_1,\dots,a_k\}[/math] be a finite set of vectors in [math]{\mathbb Z}^n[/math]. The integer cone of A is the set of vectors arising as nonnegative integer combinations of vectors in A:
[math]\mbox{int.cone}(A)=\left\{\sum_{i=1}^{k} \lambda_i a_i:\ \lambda_i \in {\mathbb Z}_+\ (i=1,\dots,k)\right\}.[/math]
The Carathéodory rank of the set A is the smallest integer t such that every vector in int.cone(A) is the nonnegative integer combination of at most t vectors in A.
Sebő [1] proved that if A is a Hilbert basis, then the Carathéodory rank of A is at most [math]2n-2[/math]. Note that deciding if A is a Hilbert basis is a coNP-complete problem, even for 0-1 vectors [2]. Bruns et al.[3] showed an example where the Carathéodory rank is more than n (in fact, they showed that in n dimensions the maximal Carathéodory rank is at least [math]\lfloor 7/6 \rfloor n[/math]). It is open if it can be upper bounded by [math](2-\varepsilon)n[/math] for some [math]\varepsilon[/math].
References
- ↑ A. Sebő, Hilbert bases, Carathéodory’s theorem and combinatorial optimization, in: R. Kannan, W.R. Pulleyblank (Eds.), Integer Programming and Combinatorial Optimization, Univ. of Waterloo Press, Waterloo, Canada, 1990, pp. 431–455, Author link
- ↑ J. Pap, Recognizing conic TDI systems is hard, DOI link
- ↑ W. Bruns, J. Gubeladze, M. Henk, A. Martin, R. Weismantel, A counterexample to an integer analogue of Carathéodory’s theorem, J. Reine Angew. Math. 510 (1999) 179–185. DOI link, Author link
