Continuous Hirsch conjecture
Continuous Hirsch conjecture
For a polytope of dimension defined by inequalities and a linear objective function , let be the total curvature of its central path. Let be the largest such total curvature over all such and . Continuous Hirsch conjecture. There is a constant such that
for all and , equivalently . The previously proposed constant and linear-in-dimension bounds for central-path curvature were disproved by constructions showing exponential growth in and, for fixed , .
Sources & referencesView supporting material
Primary source
Edward D. Kim and Francisco Santos, “An update on the Hirsch conjecture”, arXiv:0907.1186 (2009).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.