ISSN:
1439-6912
Keywords:
52 A 25
;
90 C 10
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
Notes:
Abstract We give an upper bound on the number of vertices ofP I , the integer hull of a polyhedronP, in terms of the dimensionn of the space, the numberm of inequalities required to describeP, and the size ϕ of these inequalities. For fixedn the bound isO(m n ϕ n− ). We also describe an algorithm which determines the number of integer points in a polyhedron to within a multiplicative factor of 1+ε in time polynomial inm, ϕ and 1/ε when the dimensionn is fixed.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01191202
Permalink