论文标题
五颜六色的Steinitz引理，并应用用于阻止整数程序的应用
A Colorful Steinitz Lemma with Applications to Block Integer Programs
论文作者
论文摘要
dimension $ d $中的steinitz常数是最小的值$ c（d）$，因此，对于$ \ mathbb {r}^{d} $的任何规范，对于单位球中的任何有限的零和序列，可以将序列中的任何有限的零和序列置于输入，使每个部分总和的规范限制为$ c（d）$。 Grinberg和Sevastyanov证明了$ c（d）\ le d $，而$ d $的界限最适合任意规范；我们将它们的结果称为Steinitz引理。我们提出了一次置入多个序列的Steinitz引理的变体。我们称之为五颜六色的Steinitz引理的结果表明了与序列数量无关的上限。 整数编程理论中的许多结果都通过置于有限规范的向量证明。这包括接近度结果，刻板基础算法和动态程序。由于最近关于Eisenbrand和Weismantel的论文，人们对如何使用Steinitz Lemma进行了大量研究，以改善整数编程结果。作为一个应用程序，我们证明了块结构整数程序的接近度结果。
The Steinitz constant in dimension $d$ is the smallest value $c(d)$ such that for any norm on $\mathbb{R}^{ d}$ and for any finite zero-sum sequence in the unit ball, the sequence can be permuted such that the norm of each partial sum is bounded by $c(d)$. Grinberg and Sevastyanov prove that $c(d) \le d$ and that the bound of $d$ is best possible for arbitrary norms; we refer to their result as the Steinitz Lemma. We present a variation of the Steinitz Lemma that permutes multiple sequences at one time. Our result, which we term a colorful Steinitz Lemma, demonstrates upper bounds that are independent of the number of sequences. Many results in the theory of integer programming are proved by permuting vectors of bounded norm; this includes proximity results, Graver basis algorithms, and dynamic programs. Due to a recent paper of Eisenbrand and Weismantel, there has been a surge of research on how the Steinitz Lemma can be used to improve integer programming results. As an application we prove a proximity result for block-structured integer programs.
