Mathematical Sciences: Computational Complexity of Linear Programming and Polynomial Zero Approximation

数学科学：线性规划和多项式零逼近的计算复杂性

• 批准号: 8800835
• 负责人: James Renegar
• 金额: $ 17.86万
• 依托单位: Cornell University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1988
• 资助国家: 美国
• 起止时间: 1988-06-01 至 1991-11-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=8800835&HistoricalAwards=false
• 关键词: Mathematical; Sciences; Computational; Complexity; Linear

Two areas of research are proposed: the computational complexity of approximating zeros of polynomials and systems of polynomials. The main focus of the proposed projects on linear programming is on interior algorithms. The primary objective of these projects is to develop a better understanding ot the mathematics underlying the algorithms so that provably efficient modifications to the algorithms can be made. Both worst-case and average-case measures of efficiency are to be considered. The goal of the proposed projects on polynomial zero approximation is to develop mathematics which is useful for constructing theoretically fast algorithms and useful for proving results regarding the inherent difficulty of the zero approximation problem.

提出了两个方面的研究：逼近多项式零点的计算复杂性和多项式组。所提议的线性规划项目的主要焦点是内部算法。这些项目的主要目标是更好地理解算法背后的数学原理，以便能够对算法进行经证明有效的修改。最坏情况和平均情况下的效率衡量标准都要考虑。所提出的关于多项式零逼近的项目的目标是发展数学，该数学有助于构造理论上的快速算法，并且有助于证明关于零逼近问题的固有困难的结果。