{"id":"arxiv/2606.13579","url":"https://arxiv.org/abs/2606.13579","tags":["math.OC","math.CO"],"score":0,"title":"Optimal Proximity Bound and Product Function Estimates in Integer Linear Programming","domain":"math.OC","source":"arxiv","authors":["Iskander Aliev","Gennadiy Averkov","William Jones","Timm Oertel"],"reviews":0,"subject":"math.OC","summary":"We obtain an optimal proximity bound for integer linear programs in standard form max{cx: Ax=b, x nonnegative integer}, where A is an integer mxn matrix of rank m<n and b is an integer vector. Specifically, we show that the Euclidean distance from any optimal vertex solution of the LP relaxation to a nearest optimal integer solution is bounded by $\\sqrt{\\det(AA^t)}-1$ and that this estimate is asymptotically tight. We also derive bounds for the optimal integer solutions involving the product function $\\prod_{i=1}^{n}(x_i+1)$ and discuss their applications in the knapsack setting.","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-06-11","reactions":{}}