A polynomial oracle-time algorithm for convex integer minimization
A polynomial oracle-time algorithm for convex integer minimization
复制标题
凸整数最小化的多项式预言时间算法
DOI：
--
复制
发表时间：
2007
影响因子：
2.7
通讯作者：
R. Weismantel
中科院分区：
文献类型：
--
作者：
R. Hemmecke;S. Onn;R. Weismantel
在本文中，我们考虑了通过贪婪的增强程序解决某些凸整数最小化问题的解决方案。我们表明，贪婪的增强程序仅采用某些Graver基地的方向，只需要多个多项式的增强步骤即可解决给定的问题。我们将这些结果扩展到凸出n倍整数最小化问题，并凸出2阶段随机整数最小化问题。最后，我们提出了一些凸n折内整数最小化问题的应用，我们的方法为此提供多项式时间解算法。
In this paper we consider the solution of certain convex integer minimization problems via greedy augmentation procedures. We show that a greedy augmentation procedure that employs only directions from certain Graver bases needs only polynomially many augmentation steps to solve the given problem. We extend these results to convex N-fold integer minimization problems and to convex 2-stage stochastic integer minimization problems. Finally, we present some applications of convex N-fold integer minimization problems for which our approach provides polynomial time solution algorithms.