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, Wroclaw, Poland, 3-5 July 2024. Published in: Vygen, Jens and Byrka, Jaroslaw eds. Integer Programming and Combinatorial Optimization: 25th International Conference, IPCO 2024, Wroclaw, Poland, July 3–5, 2024, Proceedings. Association for Computing Machinery, pp. 1-13. 10.1007/978-3-031-59835-7_1

Preview

PDF (IPCO accepted paper) - Accepted Post-Print Version Download (377kB) | Preview

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)
Date Type:	Published Online
Status:	Published
Schools:	Mathematics
Publisher:	Association for Computing Machinery
Date of First Compliant Deposit:	23 April 2024
Date of Acceptance:	15 March 2024
Last Modified:	09 Nov 2024 14:15
URI:	https://orca.cardiff.ac.uk/id/eprint/168221

Actions (repository staff only)

Edit Item