Cardiff University | Prifysgol Caerdydd ORCA
Online Research @ Cardiff 
WelshClear Cookie - decide language by browser settings

Proximity bounds for random integer programs

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

[thumbnail of s10107-022-01786-8.pdf]
PDF - Published Version
Available under License Creative Commons Attribution.

Download (341kB) | Preview


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

Actions (repository staff only)

Edit Item Edit Item


Downloads per month over past year

View more statistics