A polynomial oracle-time algorithm for convex integer minimization

• 成果类型: Article
• 署名作者: Hemmecke, Raymond; Onn, Shmuel; Weismantel, Robert
• 署名单位: Otto von Guericke University; Technion Israel Institute of Technology
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-009-0276-7
• 发表日期: 2011
• 页码: 97-117
• 关键词: test sets; PROGRAMS

摘要

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.