Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Alexander Barvinok (1994) pioneered an algorithmic theory of computing the exact number of lattice points of a given rational polytope. The method is based on multivariate rational functions that encode lattice-point sets of rational polyhedra as generating functions. The encoding and all related algorithms are polynomial, whenever the dimension is a fixed constant. Thus this theory implies a strengthening of H. W. Lenstra's (1983) polynomiality result for the integer feasibility problem of polytopes in fixed dimension. I present several recent results using this technique in the domain of integer linear and non-linear optimization and algorithmic game theory. In particular: 1. fully polynomial-time approximation schemes for the optimization of a polynomial function (without any convexity assumption) over the mixed-integer points of polytopes of fixed dimension 2. polynomial-time algorithms to exactly determine the number of Pareto optima and Pareto strategies of multicriteria integer linear programs, and efficient algorithms for other fundamental questions for such programs, when the strategy space is of fixed dimension 3. algorithms for computing pure Nash equilibria of certain games, and related data in game-theoretic settings.