Combinatorics, Geometry, and Algorithms

主要研究者：Barvinok，亚历山大 提案编号：DMS -0856640机构：密歇根大学安娜堡分校标题：组合数学，几何学和几何学首席研究员打算研究组合枚举和优化中的一些问题，其中算法问题和几何方法起着核心作用。该项目旨在开发计算效率高的方法来枚举高维多面体中的整数点（例如具有指定行和列和的非负矩阵多面体），单位球面上多元多项式的优化，计算复杂凸体的简单近似（例如与组合优化的困难问题相关的多面体），以及具有许多面的对称多面体的构造。本文将研究多面体中随机整数点的相关结构问题和双随机矩阵积和式的集中问题。在组合学和离散优化中，我们经常对非常大但有限的集合的结构感兴趣，因为集合的大小和经典分析的方法不适用于直接枚举是非常昂贵或不可能的，因为对象的离散特性。该项目旨在开发计算效率高的渐近方法来解决几个困难的问题，这些问题涉及大型离散集的计数和优化，并描述来自这样一个集合的典型对象的结构。几个考虑的问题是感兴趣的统计，物理和工程。

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.