Computing the integer programming gap

被引：16

作者：

Hosten, Serkan

Sturmfels, Bernd

机构：

[1] San Francisco State Univ, Dept Math, San Francisco, CA 94530 USA

[2] Univ Calif Berkeley, Dept Math, Berkeley, CA 94720 USA

来源：

COMBINATORICA | 2007年 / 27卷 / 03期

基金：

美国国家科学基金会;

关键词：

13P10; 90C10;

D O I：

10.1007/s00493-007-2057-3

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We determine the maximal gap between the optimal values of an integer program and its linear programming relaxation, where the matrix and cost function are fixed but the right hand side is unspecified. Our formula involves irreducible decomposition of monomial ideals. The gap can be computed in polynomial time when the dimension is fixed.

引用

页码：367 / 382

页数：16

共 21 条

[1] [Anonymous], 1998, USING ALGEBRAIC GEOM, DOI DOI 10.1007/978-1-4757-6911-1
[2] Short rational generating functions for lattice point problems
Barvinok, A
Woods, K
[J]. JOURNAL OF THE AMERICAN MATHEMATICAL SOCIETY, 2003, 16 (04) : 957 - 979
[3] Barvinok A., 1999, Math. Sci. Res. Inst. Publ., V38, P91
[4] Cox L. H., 1989, Annals of Operations Research, V20, P141, DOI 10.1007/BF02216926
[5] Effective lattice point counting in rational convex polytopes
De Loera, JA
Hemmecke, R
Tauzer, J
Yoshida, R
[J]. JOURNAL OF SYMBOLIC COMPUTATION, 2004, 38 (04) : 1273 - 1302
[6] Develin M., 2003, ANN COMB, V7, P441
[7] Bounds for cell entries in contingency tables given marginal totals and decomposable graphs
Dobra, A
Fienberg, SE
[J]. PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA, 2000, 97 (22) : 11885 - 11892
[8] EISEENBUD D, 2001, MATH COMPUTATIONS MA, V8
[9] Hosten S, 1999, MATH RES LETT, V6, P83
[10] Standard pairs and group relaxations in integer programming
Hosten, S
Thomas, RR
[J]. JOURNAL OF PURE AND APPLIED ALGEBRA, 1999, 139 (1-3) : 133 - 157

← 1 2 3 →