Proximity bounds for random integer programs
OPEN ACCESS
Loading...
Author / Producer
Date
2023-02
Publication Type
Journal Article
ETH Bibliography
yes
Citations
Altmetric
OPEN ACCESS
Data
Rights / License
Abstract
We study proximity bounds within a natural model of random integer programs of the type max c(inverted perpendicular) x : Ax = b, x is an element of Z(>= 0), where A is an element of Z(mxn) is of rank m, b is an element of Z(m) and c is an element of Z(n). In particular, we seek bounds for proximity in terms of the parameter Delta( A), which is the square root of the determinant of the Gram matrix AA(inverted perpendicular) of A. We prove that, up to constants depending on n and m, the proximity is "generally" bounded by Delta(A)(1/(n-m)), which is significantly better than the best deterministic bounds which are, again up to dimension constants, linear in Delta( A).
Permanent link
Publication status
published
External links
Editor
Book title
Journal / series
Volume
197 (2)
Pages / Article No.
1201 - 1219
Publisher
Springer
Event
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Organisational unit
03873 - Weismantel, Robert / Weismantel, Robert