论文标题
使用稀疏性改善接近度
Improving proximity bounds using sparsity
论文作者
论文摘要
我们将整数程序的最佳解决方案及其线性放松之间的距离称为接近度。在2018年，艾森布兰德（Eisenbrand）和魏斯曼特尔（Weismantel）证明，接近性与标准形式的计划的维度无关。我们利用现有和新颖的成果在整数解决方案的稀疏性上提高了界限。我们首先根据约束矩阵中任何全维辅修器的最大绝对值限制接近性，并且该界限紧密到约束数量中的多项式因素。在有效地将程序转换为等效的矩阵之后，我们还根据约束矩阵中最大的绝对输入提供了改进的界限。我们的结果是根据一般稀疏性界定的，因此稀疏解决方案的任何新结果都会立即改善我们的工作。还讨论了对混合整数程序的概括。
We refer to the distance between optimal solutions of integer programs and their linear relaxations as proximity. In 2018, Eisenbrand and Weismantel proved that proximity is independent of the dimension for programs in standard form. We improve their bounds using existing and novel results on the sparsity of integer solutions. We first bound proximity in terms of the largest absolute value of any full-dimensional minor in the constraint matrix, and this bound is tight up to a polynomial factor in the number of constraints. We also give an improved bound in terms of the largest absolute entry in the constraint matrix, after efficiently transforming the program into an equivalent one. Our results are stated in terms of general sparsity bounds, so any new results on sparse solutions immediately improves our work. Generalizations to mixed integer programs are also discussed.
