New Bounds for the Integer Carathéodory Rank

DOI10.1137/23M1561312arXiv2211.03150MaRDI QIDQ6136661FDOQ6136661

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)

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$.

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

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

zbMATH Keywords

Hilbert basisinteger optimizationinteger Carathéodory rank

Mathematics Subject Classification ID

Integer programming (90C10)

Cites Work

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

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)