ISSN:
1439-6912
Schlagwort(e):
52 A 25
;
90 C 10
Quelle:
Springer Online Journal Archives 1860-2000
Thema:
Mathematik
Notizen:
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.
Materialart:
Digitale Medien
URL:
http://dx.doi.org/10.1007/BF01191202
Permalink