Complexity of the Simplex Method

单纯形法的复杂性

• 批准号: 9625425
• 负责人: Nagabhushana Prabhu
• 金额: $ 2.5万
• 依托单位: Purdue Research Foundation
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1996
• 资助国家: 美国
• 起止时间: 1996-04-15 至 1998-03-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9625425&HistoricalAwards=false
• 关键词: Complexity; Simplex; Method

This is a proposal to intestigate the celebrated Hirsch conjecture using the new theoretical framework that was developed recently by the investigator and collaborators for resolving the conjecture. In contrast to all of the previous attacks on the conjecture which were inherently combinatorial, the new strategy brings to bear on the conjecture the powerful machinery of continuous analysis and representation theory of continuous groups. Preliminary results from the new approach include (i) the discovery of a new formulation of the Hirsch conjecture with connections to Gaussian elimination, and (ii) the emergence of the most compelling theoretical and empirical evidence to date about the validity of not just the Hirsch conjecture but a considerably stronger version of it. The project aims at proving the strong Hirsch conjecture by employing powerful techniques from differential geometry and cohomology theory. The strong Hirsch conjecture, if proved, would show the existence of exponentially many paths of linear length between the initial and optimal vertices of a polyhedron, and would hence revitalize the research for polynomial-time Simplex algorithms. ***

这是一个建议，intestigate著名的赫希猜想使用的新的理论框架，最近开发的研究者和合作者解决的猜想。 在对比所有以前的攻击猜想这是固有的组合，新的战略带来承担猜想的强大机器的连续分析和表示理论的连续群。 新方法的初步结果包括：（i）发现了赫希猜想的一个新公式，并与高斯消去法相联系;（ii）出现了迄今为止最令人信服的理论和经验证据，不仅证明了赫希猜想的有效性，而且证明了它的一个更强的版本。 该项目的目的是证明强赫希猜想采用强大的技术，从微分几何和上同调理论。 强Hirsch猜想如果被证明，将表明多面体的初始顶点和最优顶点之间存在指数级多条线性长度的路径，从而将振兴多项式时间单纯形算法的研究。 ***