Combinatorics, Geometry, and Algorithms

点击翻译按钮获取中文摘要

ABSTRACTPrincipal Investigator: Barvinok, Alexander Proposal Number: DMS - 0856640Institution: University of Michigan Ann ArborTitle: Combinatorics, Geometry, and AlgorithmsThe Principal Investigator intends to work on a number of problems in combinatorial enumeration and optimization, with algorithmic questions and geometric approaches playing the central role. The project aims to develop computationally efficient approaches to enumeration of integer points in higher-dimensional polyhedra (such as polyhedra of non-negative matrices with prescribed row and column sums), optimization of multivariate polynomials on the unit sphere, computing simple approximations of complicated convex bodies (such as polytopes associated with hard problems of combinatorial optimization), and construction of symmetric polytopes with many faces. Related structural questions concerning random integer points in polyhedra and concentration of permanents of doubly stochastic matrices will be investigated. In combinatorics and discrete optimization we are often interested in the structure of very large, yet finite sets, where direct enumeration is prohibitively expensive or impossible because of the size of the sets and methods of classical analysis are not applicable because of the discrete character of objects. The project aims to develop computationally efficient asymptotic approaches to several hard problems which concern counting and optimization in large discrete sets and describing the structure of a typical object from such a set. Several of the considered problems are of interest to statistics, physics, and engineering.