Proximity Results and Faster Algorithms for Integer Programming Using the Steinitz Lemma
Proximity Results and Faster Algorithms for Integer Programming Using the Steinitz Lemma
复制标题
使用斯坦尼茨引理进行整数规划的邻近结果和更快的算法
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
R. Weismantel
中科院分区：
文献类型：
--
作者：
F. Eisenbrand;R. Weismantel
我们考虑标准形式 max { cTx : Ax = b, x⩾ 0, x ε Zn} 的整数规划问题，其中 A ε Zm × n，b ε Zm，c ε Zn。我们证明这样的整数规划可以在时间 (m ⋅ Δ)O(m) ⋅ Vert bVert∞2 内求解，其中 Δ 是 A 中条目的每个绝对值的上限。这改进了 Papadimitriou [27] 的 (m⋅ Δ)O(m2) 的长期最佳界限，其中，b 的条目的绝对值也需要以 Δ 为界。我们的结果依赖于 Steinitz 的引理，该引理指出 Rm 中包含在范数的单位球中并且总和为零的向量可以排序，使得所有部分和都具有以 m 为界的范数。我们还使用 Steinitz 引理来证明，最优整数和分数解的 ℓ1-距离（同样在变量存在上限的情况下）以 m ⋅ (2,m⋅ Δ +1)m 为界。这里 Δ 又是 A 的条目绝对值的上限。我们的界限的新颖之处在于它与 n 无关。我们通过将其应用于一般的背包问题来为我们的界限的重要性提供证据，在该问题中我们获得了改进最近文献的结构和算法结果。
We consider integer programming problems in standard form max { cTx : Ax = b, x⩾ 0, x ∈ Zn} where A ∈ Zm × n, b ∈ Zm, and c ∈ Zn. We show that such an integer program can be solved in time (m ⋅ Δ)O(m) ⋅ Vert bVert∞2, where Δ is an upper bound on each absolute value of an entry in A. This improves upon the longstanding best bound of Papadimitriou [27] of (m⋅ Δ)O(m2), where in addition, the absolute values of the entries of b also need to be bounded by Δ. Our result relies on a lemma of Steinitz that states that a set of vectors in Rm that is contained in the unit ball of a norm and that sum up to zero can be ordered such that all partial sums are of norm bounded by m. We also use the Steinitz lemma to show that the ℓ1-distance of an optimal integer and fractional solution, also under the presence of upper bounds on the variables, is bounded by m ⋅ (2,m⋅ Δ +1)m. Here Δ is again an upper bound on the absolute values of the entries of A. The novel strength of our bound is that it is independent of n. We provide evidence for the significance of our bound by applying it to general knapsack problems where we obtain structural and algorithmic results that improve upon the recent literature.