Research Initiation Award: Polar Geometric Approach to Linear Programming

研究启动奖：线性规划的极坐标几何方法

• 批准号: 9308953
• 负责人: Nagabhushana Prabhu
• 金额: $ 9万
• 依托单位: Purdue Research Foundation
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1993
• 资助国家: 美国
• 起止时间: 1993-10-01 至 1997-03-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9308953&HistoricalAwards=false
• 关键词: Research; Initiation; Award; Polar; Geometric

9308953 Prabhu The research will investigate a new approach to Linear Programming (LP). The approach exploits fundamental results from Convex Polytope Theory and Polarity Theory that have not been applied to LP computation previously. Preliminary studies suggest that the approach has prospects of yielding an efficient algorithm that could be faster than the current LP algorithms. The work describes two methods for devising an efficient LP algorithm based on the suggested approach: Gale Transform Method and Simplicial Refinement Method. The methods apply classic results on the combinatorial and metric structure of polytopes to make computation efficient. Computational experiments on the methods will be undertaken in parallel with theoretical investigations in order to ensure that the resulting algorithm will be theoretically efficient. Enormous theoretical and computational research effort has been expended in the past on attempts to convert the edge-following Simplex method into a worst-case polynomial-time algorithm . The Generalized Simple scheme can be significant, in that it proffers a fresh approach to the quest for worst-case polynomial-time Simplex algorithms. If these goals are achieved, the results will have significant impact in solving real world problems.

小行星9308953 这项研究将探讨一种新的方法， 编程（LP）。 该方法利用了以下基本结果： 凸多面体理论和极性理论，尚未被 以前的LP计算。 初步研究表明 这种方法有可能产生一种有效的算法， 这可能比当前的LP算法更快。 工作 描述了两种方法，用于设计一个有效的LP算法， 关于建议的方法：大风变换法和单纯形 炼制方法。 该方法将经典结果应用于 组合和度量结构的多面体，使 计算效率高。 方法的计算实验 将与理论研究同时进行， 为了确保所得到的算法在理论上 高效. 大量的理论和计算研究工作 在过去，人们一直试图将边缘跟踪 单纯形法转化为最坏情况的多项式时间算法。 的 广义简单方案可能是重要的，因为它提供了 寻求最坏情况多项式时间的新方法 单纯形算法。 如果这些目标得以实现， 对解决真实的世界问题有重大影响。