Mathematical Sciences: Algebraic Methods in Optimization

数学科学：优化中的代数方法

• 批准号: 9501129
• 负责人: Alexander Barvinok
• 金额: $ 6万
• 依托单位: Regents of the University of Michigan - Ann Arbor
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1995
• 资助国家: 美国
• 起止时间: 1995-07-01 至 1999-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9501129&HistoricalAwards=false
• 关键词: Mathematical; Sciences; Algebraic; Methods; Optimization

This award supports the research of Professor Alexandre Barvinok on the construction of algorithms for computational problems in combinatorics and algebra. The main goal is to find non-trivial upper bounds for the computational complexity of these problems by exploring the underlying algebraic structure. Three specific topics are being investigated. The first topic includes the applications of exponential sums to a wide range of computational problems. The second deals with applications of the representation theory of the symmetric group to hard problems in combinatorial optimization. The third topic involves quantifier elimination in integer programming, a specific unresolved question concerning integral points in polyhedra. The algorithms developed have potential practical applications to real world problems that reduce to hard enumeration. This research is in the general area of Combinatorics. Combinatorics attempts to find efficient methods to study how discrete collections of objects can be arranged. The behavior of discrete systems is extremely important to modern communications. For example, the design of large networks, such as those occurring in telephone systems, and the design of algorithms in computer science deal with discrete sets of objects, and this makes use of combinatorial research.

该奖项支持Alexandre Barvinok教授在组合学和代数计算问题的算法构建方面的研究。主要目标是通过探索底层代数结构来找到这些问题计算复杂度的非平凡上界。目前正在调查三个具体问题。第一个主题包括指数和在广泛计算问题中的应用。第二章讨论了对称群的表示理论在组合优化难题中的应用。第三个主题涉及整数规划中的量词消去，这是一个关于多面体中积分点的具体未解决的问题。所开发的算法对于简化为难枚举的现实世界问题具有潜在的实际应用。这项研究属于组合学的一般领域。组合学试图找到有效的方法来研究离散的对象集合如何排列。离散系统的行为对现代通信极为重要。例如，大型网络的设计，比如那些出现在电话系统中的网络，以及计算机科学中处理离散对象集的算法设计，这就利用了组合研究。