论文标题
距离距离polyhedra的顶点的距离距离转移
Distance-sparsity transference for vertices of corner polyhedra
论文作者
论文摘要
我们获得了角落多面体顶点的转移，该转角连接了两个公认的研究领域：解决方案与整数程序的邻近性和稀疏性。在背包方案中，它对先前已知的接近度估计值进行了指数改进（以解决方案的支持大小）。此外，对于一般整数线性程序，我们获得了一个类似的结果，该结果将最佳解决方案的最小绝对非零输入与其支持的大小相关联。
We obtain a transference bound for vertices of corner polyhedra that connects two well-established areas of research: proximity and sparsity of solutions to integer programs. In the knapsack scenario, it gives an exponential (in the size of support of a solution) improvement on previously known proximity estimates. In addition, for general integer linear programs we obtain a resembling result that connects the minimum absolute nonzero entry of an optimal solution with the size of its support.
