Proximity bounds for random integer programs
成果类型：
Article
署名作者：
Celaya, Marcel; Henk, Martin
署名单位：
Swiss Federal Institutes of Technology Domain; ETH Zurich; Technical University of Berlin
刊物名称：
MATHEMATICAL PROGRAMMING
ISSN/ISSBN：
0025-5610
DOI：
10.1007/s10107-022-01786-8
发表日期：
2023
页码：
1201-1219
关键词：
摘要：
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).