ON INTEGER POINTS IN POLYHEDRA

被引：48

作者：

COOK, W

HARTMANN, M

KANNAN, R

MCDIARMID, C

机构：

[1] BELL COMMUN RES INC,RED BANK,NJ

[2] CARNEGIE MELLON UNIV,DEPT COMP SCI,PITTSBURGH,PA 15213

[3] UNIV N CAROLINA,DEPT HLTH & SAFETY,CHAPEL HILL,NC 27514

[4] INST ECON & STAT,OXFORD,ENGLAND

[5] UNIV BONN,INST OKONOMET & OPERAT RES,W-5300 BONN,GERMANY

来源：

COMBINATORICA | 1992年 / 12卷 / 01期

关键词：

D O I：

10.1007/BF01191202

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We give an upper bound on the number of vertices of P(I), the integer hull of a polyhedron P, in terms of the dimension n of the space, the number m of inequalities required to describe P, and the size-phi of these inequalities. For fixed n the bound is O(m(n)phi(n-1)). We also describe an algorithm which determines the number of integer points in a polyhedron to within a multiplicative factor of 1 + epsilon in time polynomial in m, phi and 1/epsilon when the dimension n is fixed.

引用

页码：27 / 37

页数：11

共 25 条

[1]

BARANY I, 1989, 917 YALE U COWL F RE

[2]

Cassels J. W. S., 1971, INTRO GEOMETRY NUMBE

[3]

Cherkasskij V. D., 1984, EKONOM MAT METODY, V20, P1132

[4] 2 ALGORITHMS FOR DETERMINING VOLUMES OF CONVEX POLYHEDRA [J].

COHEN, J ;

HICKEY, T .

JOURNAL OF THE ACM, 1979, 26 (03) :401-414

[5]

DYER M, UNPUB SIAM J COMPUTI

[6]

DYER M, 1989, 8840 CARNU DEP MATH

[7] BRICK DECOMPOSITIONS AND THE MATCHING RANK OF GRAPHS [J].

EDMONDS, J ;

LOVASZ, L ;

PULLEYBLANK, WR .

COMBINATORICA, 1982, 2 (03) :247-274

[8]

Gary Michael R., 1979, COMPUTERS INTRACTABI

[9]

Grotschel M., 1988, GEOMETRIC ALGORITHMS

[10]

GRUBER PM, 1987, GEOMETRY NUMBERS

← 1 2 3 →