Sparsity and integrality gap transference bounds for integer programs

Aliev, Iskander ORCID: https://orcid.org/0000-0002-2206-9207, Celaya, Marcel ORCID: https://orcid.org/0000-0003-3480-4835 and Henk, Martin 2024. Sparsity and integrality gap transference bounds for integer programs. Presented at: IPCO 2024: The 25th Conference on Integer Programming and Combinatorial Optimization, 3-5 July 2024. IPCO Conference Proceedings. Item availability restricted.

PDF (IPCO accepted paper) - Accepted Post-Print Version Restricted to Repository staff only until 6 July 2024 due to copyright restrictions. Download (377kB)

Abstract

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 min{c·x: x in P, x integer}, where P ={x: Ax=b,x nonnegative} is a polyhedron in the standard form determined by an integer m × n matrix A and an integer vector b. The main result of the paper gives an upper bound for the integrality gap that drops exponentially in the size of the support of the optimal solutions corresponding to the vertices of the integer hull of P. Additionally, we obtain a new proximity bound that estimates the l2-distance from a vertex of P to its nearest integer point in the polyhedron P. The proofs make use of the results from the geometry of numbers and convex geometry.

Item Type:	Conference or Workshop Item (Paper)
Status:	In Press
Schools:	Mathematics
Date of First Compliant Deposit:	23 April 2024
Date of Acceptance:	15 March 2024
Last Modified:	04 May 2024 02:56
URI:	https://orca.cardiff.ac.uk/id/eprint/168221

Actions (repository staff only)

Edit Item