Complexity of the Simplex Method
Complexity of the Simplex Method
批准号:
9625425
负责人:
Nagabhushana Prabhu
金额:
$2.5万
依托单位国家:
美国
项目类别:
Standard Grant
财政年份:
1996
资助国家:
美国
项目状态:
已结题
起止时间:
1996-04-15 至 1998-03-31
中文摘要
这是一个研究赫希猜想的建议,使用研究者和合作者最近为解决这个猜想而开发的新的理论框架。与以往所有对猜想的固有组合性攻击不同,新策略将连续分析和连续群表示理论的强大机制引入到猜想中。新方法的初步结果包括:(i)发现了与高斯消去有关的赫希猜想的新公式,以及(ii)迄今为止最令人信服的理论和经验证据的出现,这些证据不仅证明了赫希猜想的有效性,而且证明了它的一个相当强大的版本。该项目旨在利用微分几何和上同调理论的强大技术证明强赫希猜想。强赫希猜想,如果得到证明,将表明多面体的初始顶点和最优顶点之间存在指数多的线性长度路径,从而使多项式时间单纯形算法的研究重新焕发活力。***
英文摘要
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. ***
期刊论文(0)
专著(0)
科研奖励(0)
会议论文
Hirsch Conjecture and Linear Programming
-
批准号:9800053
-
项目类别:Standard Grant
-
资助金额:$9.82万
-
财政年份:1998
-
负责人:Nagabhushana Prabhu
-
依托单位:
SGER: New Approaches for Design of Nonlinear Discriminants
-
批准号:9527477
-
项目类别:Standard Grant
-
资助金额:$3.0万
-
财政年份:1995
-
负责人:Nagabhushana Prabhu
-
依托单位:
Research Initiation Award: Polar Geometric Approach to Linear Programming
-
批准号:9308953
-
项目类别:Continuing Grant
-
资助金额:$9.0万
-
财政年份:1993
-
负责人:Nagabhushana Prabhu
-
依托单位:
海外基金