Complexity in Geometric Combinatorics

几何组合的复杂性

• 批准号: 0400617
• 负责人: Alexander Barvinok
• 金额: --
• 依托单位: Regents of the University of Michigan - Ann Arbor
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2004
• 资助国家: 美国
• 起止时间: 2004-07-01 至 2011-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0400617&HistoricalAwards=false
• 关键词: Complexity; Geometric; Combinatorics

The project aims at developing geometric methods to solve a variety of algorithmicproblems regarding various combinatorial structures. The problems includeenumeration of lattice points in certain sets (such as sets defined by formulas of Presburger arithmetic), asymptotic counting of combinatorial structures of agiven type (such as bases in matroids), and understanding metric and combinatorial properties of some universal convex bodies (such as the convex cone of non-negative multivariate polynomials). The proposed approaches include developing computationally efficient techniques of working with multivariate rational functions, understanding properties of very large finite metric spaces, and applying methodsfrom convex geometry.In combinatorics, we are interested in working with finite, although very large, sets,where methods of classical analysis often fail because the main objects are no longersmooth but discrete. The project aims at developing efficient computational methodsfor some previously intractable problems dealing with exact or approximateenumeration in very large sets and finding maximum (minimum) of functions definedon large sets. Many of the considered problems are of interest to statistics, physicsand optimization.

该项目旨在开发几何方法来解决各种组合结构的各种算法问题。这些问题包括某些集合（如由Presburger算术公式定义的集合）中格点的计数，给定类型的组合结构（如拟阵中的基）的渐近计数，以及理解某些泛凸体（如非负多元多项式的凸锥）的度量和组合性质。提出的方法包括发展计算效率高的多元有理函数的技术，理解非常大的有限度量空间的性质，以及应用凸几何的方法。在组合学中，我们对有限的，尽管非常大的，集合的工作感兴趣，经典分析的方法经常失败，因为主要对象不再是光滑的，而是离散的。该项目的目的是为一些以前难以解决的问题开发有效的计算方法，这些问题涉及在非常大的集合中进行精确或近似的计数，并找到定义在大集合上的函数的最大值（最小值）。 所考虑的许多问题都是统计学、物理学和最优化所感兴趣的。