- How good are interior point methods? Klee-Minty cubes tighten iteration-complexity bounds. Antoine Deza (dezamcmaster.ca) Eissa Nematollahi (nematoemcmaster.ca) Tamas Terlaky (terlakymcmaster.ca) Abstract: By refining a variant of the Klee-Minty example that forces the central path to visit all the vertices of the Klee-Minty n-cube, we exhibit a nearly worst-case example for path-following interior point methods. Namely, while the theoretical iteration-complexity upper bound is O(2^{n}n^{\frac{5}{2}}), we prove that solving this n-dimensional linear optimization problem requires at least $2^n-1$ iterations. Keywords: Linear programming, interior point method, worst-case iteration-complexity Category 1: Linear, Cone and Semidefinite Programming Category 2: Linear, Cone and Semidefinite Programming (Linear Programming ) Citation: AdvOL-Report #2004/20 Advanced Optimization Laboratory, Department of Computing and Software, McMaster University, Hamilton, Ontario, Canada, December 2004. Download: [Postscript][PDF]Entry Submitted: 12/31/2004Entry Accepted: 12/31/2004Entry Last Modified: 02/05/2006Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Programming Society and by the Optimization Technology Center.