Return to Colloquia & Seminar listing
Efficient counting of integer points in rational polytopes and integer programming
Student-Run Research Seminar| Speaker: | Alexander Barvinok,, Univ. of Michigan Ann Arbor |
| Location: | 593 Kerr |
| Start time: | Tue, Apr 18 2000, 3:10PM |
Consider a family of convex rational polytopes obtained from a given polytope by moving its facets parallel to themselves so that the overall combinatorial structure of the polytope doesn't change. Then the number of integer points in a polytope from the family is expressed by a polynomial in the floor-type functions of the displacements of the facets. Furthermore, in any fixed dimension, this polynomial can be efficiently computed. This gives rise to a new polynomial time algorithm in (parametric) integer programming in fixed dimension.