Continuous Hirsch Conjecture for central-path curvature

About 16 years old · traced to

Let Λ(n,d)\Lambda(n,d) denote the largest total curvature of a central path over polytopes defined by nn inequalities in dimension dd and over all linear objectives.

Continuous Hirsch Conjecture.

Λ(n,d)∈O(n).\Lambda(n,d) \in O(n).

Equivalently, there is a constant KK such that Λ(n,d)≤Kn\Lambda(n,d) \leq Kn for all nn and dd.

The source explains that known lower bounds make this conjectured linear behavior asymptotically tight. Its status is not resolved in the supplied material.

References

Primary source

Edward D. Kim, “Geometric Combinatorics of Transportation Polytopes and the Behavior of the Simplex Method”, arXiv:1006.2416 (2010).

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.