New Bounds for the Integer Carathéodory Rank - Aliev, Iskander; Henk, Martin; Hogan, Mark; Kuhlmann, Stefan; Oertel, Timm (SIAM Journal on Optimization, 2024)
Given a rational pointed n-dimensional cone C, we study the integer Carathéodory rank CR(C) and its asymptotic form CRa(C), where we consider “most” integer vectors in the cone. The main result significantly improves the previously known upper bound for CRa(C). We also study bounds on CR(C) in terms of Δ, the maximal absolute n×n minor of the matrix given in an integral polyhedral representation of C. If Δ∈1,2, we show that CR(C)=n, and prove upper bounds for simplicial cones, improving the best known upper bound on CR(C) for Δ≤n. n-dimensional cone C, we study the integer Carathéodory rank CR(C) and its asymptotic form CRa(C), where we consider “most” integer vectors in the cone. The main result significantly improves the previously known upper bound for CRa(C). We also study bounds on CR(C) in terms of Δ, the maximal absolute n×n minor of the matrix given in an integral polyhedral representation of C. If Δ∈1,2, we show that CR(C)=n, and prove upper bounds for simplicial cones, improving the best known upper bound on CR(C) for Δ<br
Keywords: integer optimization; Hilbert basis; integer Carathéodory rank