论文标题
关于$δ$ - 模块化ILP和LP之间的简单连接，以及整数顶点的新界限
On a Simple Connection Between $Δ$-modular ILP and LP, and a New Bound on the Number of Integer Vertices
论文作者
论文摘要
令$ a \ in z^{m \ times n} $，$ rank（a）= n $，$ b \ in z^m $，而$ p $为$ n $ dimensional polyhedron，由系统$ a x \ leq b $引起。 众所周知的事实是，如果$ f $是$ p $的$ k $ face，那么系统至少存在$ n-k $线性独立的独立不平等，$ a x \ leq b $在$ f $上成为平等。换句话说，存在一组索引$ j $，以便$ | j | \ geq n-k $，$等级（a_ {j}）= n-k $，并且 $$ a_ {j} x -b_ {j} = 0，\ quad \ text {对于f $}中的任何$ x \。 $$ 我们表明，整数多面体也有类似的事实 $$ p_ {i} = cons.hull \ bigl（p \ cap z^n \ bigr）， $$ 如果我们还假设$ p $是$δ$ - 模块化，则对于\ {1,2，\ dots \} $中的某些$δ\。更确切地说，如果$ f $是$ p_ {i} $的$ k $ -face，则存在一组索引$ j $，以便$ | j | \ geq n-k $，$等级（a_ {j}）= n-k $，并且 $$ a_ {j} x -b_ {j} \oversetΔ{=} 0，\ quad \ text {对于f \ cap z^n $}中的任何$ x \ for任何$ x \ $$其中$ x \oversetδ{=} y $表示$ \ | x -y \ | _ {\ infty}<δ$。换句话说，系统至少存在$ n-k $线性独立的不等式$ a x \ leq b $，几乎在$ f \ cap z^n $上几乎成为平等。当我们几乎说时，我们的意思是休闲裤不大于$δ-1 $。使用这个事实，我们证明了不平等 $$ | vert（p_i）| \ leq 2 \ cdot \ binom {m} {n} \cdotΔ^{n-1}， 对于$ p_i $的顶点数量，$$比以$δ= o（n^2）$绑定的最先进的状态更好。
Let $A \in Z^{m \times n}$, $rank(A) = n$, $b \in Z^m$, and $P$ be an $n$-dimensional polyhedron, induced by the system $A x \leq b$. It is a known fact that if $F$ is a $k$-face of $P$, then there exist at least $n-k$ linearly independent inequalities of the system $A x \leq b$ that become equalities on $F$. In other words, there exists a set of indices $J$, such that $|J| \geq n-k$, $rank(A_{J}) = n-k$, and $$ A_{J} x - b_{J} = 0,\quad \text{for any $x \in F$}. $$ We show that a similar fact holds for the integer polyhedron $$ P_{I} = conv.hull\bigl(P \cap Z^n\bigr), $$ if we additionally suppose that $P$ is $Δ$-modular, for some $Δ\in \{1,2,\dots\}$. More precisely, if $F$ is a $k$-face of $P_{I}$, then there exists a set of indices $J$, such that $|J| \geq n-k$, $rank(A_{J}) = n-k$, and $$ A_{J} x - b_{J} \oversetΔ{=} 0,\quad \text{for any $x \in F \cap Z^n$}, $$ where $x \oversetΔ{=} y$ means that $\|x - y\|_{\infty} < Δ$. In other words, there exist at least $n-k$ linearly independent inequalities of the system $A x \leq b$ that almost become equalities on $F \cap Z^n$. When we say almost, we mean that the slacks are not greater than $Δ-1$. Using this fact, we prove the inequality $$ |vert(P_I)| \leq 2 \cdot \binom{m}{n} \cdot Δ^{n-1}, $$ for the number of vertices of $P_I$, which is better, than the state of the art bound for $Δ= O(n^2)$.
