Sharp Proximity Bounds for Integer Programs with Few Rows
We study the proximity between an optimal vertex of a standard form linear program with constraint matrix $A\in\mathbb{Z}^{m\times n}$ and an optimal integer solution. When $m = 2$, we prove the sharp infinity-norm bound $\Delta-1$, where $\Delta$ is the largest absolute maximal minor of $A$. When $m = 1$, we express t...