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. ***

Project Start
Project End
Budget Start
1996-04-15
Budget End
1998-03-31
Support Year
Fiscal Year
1996
Total Cost
$25,000
Indirect Cost
Name
Purdue Research Foundation
Department
Type
DUNS #
City
West Lafayette
State
IN
Country
United States
Zip Code
47907