论文标题
整数船体顶点的新界限
New Bounds for the Vertices of the Integer Hull
论文作者
论文摘要
整数船体的顶点是等效于线性程序的基本可行解决方案的组成部分。在本文中，我们对这些顶点的非零组件数量（它们的支持）给出了新的界限，以匹配最著名的界限或对它们的改进。尽管最知名的界限利用了深度技术，但我们仅利用概率理论的基本结果来利用量度效应的浓度。为了显示我们技术的多功能性，我们使用结果在此类顶点的数量和算法上提供了最著名的界限，以列举它们。我们还改进了已知的下限，以表明我们的结果几乎是最佳的。我们工作的主要成分之一是对著名的hoeffing的概括，限制为可能引起人们关注的矢量值随机变量。
The vertices of the integer hull are the integral equivalent to the well-studied basic feasible solutions of linear programs. In this paper we give new bounds on the number of non-zero components -- their support -- of these vertices matching either the best known bounds or improving upon them. While the best known bounds make use of deep techniques, we only use basic results from probability theory to make use of the concentration of measure effect. To show the versatility of our techniques, we use our results to give the best known bounds on the number of such vertices and an algorithm to enumerate them. We also improve upon the known lower bounds to show that our results are nearly optimal. One of the main ingredients of our work is a generalization of the famous Hoeffding bound to vector-valued random variables that might be of general interest.
