n-Fold integer programming in cubic time
n-Fold integer programming in cubic time
复制标题
三次整数规划
DOI：
--
复制
发表时间：
2011
影响因子：
2.7
通讯作者：
Lyubov Romanchuk
中科院分区：
文献类型：
--
作者：
R. Hemmecke;S. Onn;Lyubov Romanchuk
n 重整数规划是运筹学和统计学中各种自然应用的基本问题。此外，它是通用的，并为所有整数规划提供了一种新的、可变维度的参数化。在本文之前，最快的 n 重整数规划算法及时运行 documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document}$${O左(n^{g(A)}L
ight)}$$end{document} 其中 L 是输入数字部分的二进制长度，g(A) 是定义系统的双矩阵 A 的所谓 Graver 复杂度。在本文中，我们提供了重大改进，并建立了一种算法，该算法在时间 O (n3L) 中运行，无论双矩阵 A 如何，都具有对 n 的三次依赖性。我们的算法也适用于可分离凸分段仿射目标。此外，它可用于定义任何整数规划问题的近似层次结构。
n-Fold integer programming is a fundamental problem with a variety of natural applications in operations research and statistics. Moreover, it is universal and provides a new, variable-dimension, parametrization of all of integer programming. The fastest algorithm for n-fold integer programming predating the present article runs in time documentclass[12pt]{minimal} usepackage{amsmath} usepackage{wasysym} usepackage{amsfonts} usepackage{amssymb} usepackage{amsbsy} usepackage{mathrsfs} usepackage{upgreek} setlength{oddsidemargin}{-69pt} egin{document}$${O left(n^{g(A)}L
ight)}$$end{document} with L the binary length of the numerical part of the input and g(A) the so-called Graver complexity of the bimatrix A defining the system. In this article we provide a drastic improvement and establish an algorithm which runs in time O (n3L) having cubic dependency on n regardless of the bimatrix A. Our algorithm works for separable convex piecewise affine objectives as well. Moreover, it can be used to define a hierarchy of approximations for any integer programming problem.
通过 Graver 基实现凸整数最大化
影响因子：
0.8
作者：
J. De Loera;R. Hemmecke;Shmul Onn;U. G. Rothblum;R. Weismantel
通讯作者：
R. Weismantel