2023/11/11 by Iskander Aliev, Aliev, Iskander, Marcel Celaya +3
Engineering · Mathematics · Neuroscience · #11H31 #52C07 #90C10 #Advanced Optimization Algorithms Research #FOS: Mathematics #Nuclear Receptors and Signaling #Optimization and Control (math.OC) #Optimization and Mathematical Programming
paper · pdf · doi:10.48550/arxiv.2311.06605
openalex publication_date 2023/11/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We obtain new transference bounds that connect two active areas of research: proximity and sparsity of solutions to integer programs. Specifically, we study the additive integrality gap of the integer linear programs mincx: x in P, x integer, where P=x: Ax=b, x nonnegative is a polyhedron in the standard form determined by an integer mxn matrix A and an integer vector b. The main result of the paper shows that the integrality gap drops exponentially in the size of support of the optimal solutions that correspond to the vertices of the integer hull of the polyhedron P. Additionally, we obtain a new proximity bound that estimates the distance from any point of P to its nearest integer point in P. The proofs make use of the results from the geometry of numbers and convex geometry.