Continuous Hirsch conjecture

For a polytope PP of dimension dd defined by nn inequalities and a linear objective function cc, let λc(P)\lambda_c(P) be the total curvature of its central path. Let Λ(n,d)\Lambda(n,d) be the largest such total curvature over all such PP and cc. Continuous Hirsch conjecture. There is a constant KK such that

Λ(n,d)Kn\Lambda(n,d)\leq Kn

for all nn and dd, equivalently Λ(n,d)O(n)\Lambda(n,d)\in O(n). The previously proposed constant and linear-in-dimension bounds for central-path curvature were disproved by constructions showing exponential growth in dd and, for fixed d2d\geq 2, lim infnΛ(n,d)/nπ\liminf_{n\to\infty}\Lambda(n,d)/n\geq\pi.

Sources & referencesView supporting material

Primary source

Edward D. Kim and Francisco Santos, “An update on the Hirsch conjecture”, arXiv:0907.1186 (2009).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.