Proximity bounds for random integer programs

Celaya, Marcel ORCID: https://orcid.org/0000-0003-3480-4835 and Henk, Martin 2023. Proximity bounds for random integer programs. Mathematical Programming 197 , pp. 1201-1219. 10.1007/s10107-022-01786-8

Preview

PDF - Published Version Available under License Creative Commons Attribution. Download (341kB) | Preview

Abstract

We study proximity bounds within a natural model of random integer programs of the type maxcc⊤xx:AAxx=bb,xx∈Z≥0, where AA∈Zm×n is of rank m, bb∈Zm and cc∈Zn. In particular, we seek bounds for proximity in terms of the parameter Δ(AA), which is the square root of the determinant of the Gram matrix AAAA⊤ of AA. We prove that, up to constants depending on n and m, the proximity is “generally” bounded by Δ(AA)1/(n−m), which is significantly better than the best deterministic bounds which are, again up to dimension constants, linear in Δ(AA).

Item Type:	Article
Date Type:	Publication
Status:	Published
Schools:	Mathematics
Publisher:	Springer
ISSN:	1436-4646
Date of First Compliant Deposit:	23 February 2023
Date of Acceptance:	30 December 2021
Last Modified:	03 May 2023 08:28
URI:	https://orca.cardiff.ac.uk/id/eprint/157272

Actions (repository staff only)

Edit Item