New Bounds for the Integer Carathéodory Rank

DOI10.1137/23M1561312MaRDI QIDQ6136661zbMATH OpenFDO

Authors Iskander Aliev, Martin Henk, Mark J. Hogan, Stefan Kuhlmann, Timm Oertel

Publication date 17 January 2024

Published in SIAM Journal on Optimization (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2211.03150

zbMATH Keywords

Hilbert basisinteger optimizationinteger Carathéodory rank

Mathematics Subject Classification ID

Integer programming (90C10)

Abstract: Given a rational pointed $n$-dimensional cone $C$, we study the integer Carath'{e}odory rank $operatornameCR(C)$ and its asymptotic form $operatornameC{R}^{ma}(C)$, where we consider ``most integer vectors in the cone. The main result significantly improves the previously known upper bound for $operatornameC{R}^{ma}(C)$. We also study bounds on $operatornameCR(C)$ in terms of $Delta$, the maximal absolute $nimesn$ minor of the matrix given in an integral polyhedral representation of $C$. If $Deltainlbrace1,2brace$, we show $operatornameCR(C)=n$, and prove upper bounds for simplicial cones, improving the best known upper bound on $operatornameCR(C)$ for $Deltaleqn$.

Recommendations

• Carathéodory bounds for integer cones
• A bound on the Carathéodory number
• An integer analogue of Carathéodory's theorem
• Improved bound for the Carathéodory rank of the bases of a matroid

Cites work

• scientific article; zbMATH DE number 3987367 (Why is no real title available?)
• scientific article; zbMATH DE number 4089320 (Why is no real title available?)
• scientific article; zbMATH DE number 3001316 (Why is no real title available?)
• A counterexample to an integer analogue of Carathéodory's theorem
• A strongly polynomial algorithm for bimodular integer linear programming
• An integer analogue of Carathéodory's theorem
• Carathéodory bounds for integer cones
• Detecting the integer decomposition property and Ehrhart unimodality in reflexive simplices
• Improved bound for the Carathéodory rank of the bases of a matroid
• Improving the Cook et al. proximity bound given integral valued constraints
• Integer program with bimodular matrix
• Non-standard approaches to integer programming
• Normal polytopes: between discrete, continuous, and random
• Normality and covering properties of affine semigroups
• On lattice width of lattice-free polyhedra and height of Hilbert bases
• On the foundations of linear and integer linear programming I
• On total dual integrality
• Polyhedra with the integer Carathéodory property
• Some Basis Theorems for Integral Monoids
• Sparse Solutions of Linear Diophantine Equations
• Sparse representation of vectors in lattices and semigroups
• Weighted projective spaces and reflexive simplices

This page was built for publication: New Bounds for the Integer Carathéodory Rank

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6136661)