Optimization Online


A Simpler and Tighter Redundant Klee-Minty Construction

Eissa Nematollahi (nematoe***at***mcmaster.ca)
Tamas Terlaky (terlaky***at***mcmaster.ca)

Abstract: By introducing redundant Klee-Minty examples, we have previously shown that the central path can be bent along the edges of the Klee-Minty cubes, thus having $2^n-2$ sharp turns in dimension $n$. In those constructions the redundant hyperplanes were placed parallel with the facets active at the optimal solution. In this paper we present a simpler and more powerful construction, where the redundant constraints are parallel with the coordinate-planes. An important consequence of this new construction is that one of the sets of redundant hyperplanes is touching the feasible region, and $N$, the total number of the redundant hyperplanes is reduced by a factor of $n^2$, further tightening the gap between iteration-complexity upper and lower bounds.

Keywords: Linear programming, Klee-Minty example, interior point methods, worst-case iteration complexity, central path.

Category 1: Linear, Cone and Semidefinite Programming (Linear Programming )

Citation: Report Number: AdvOL2006/12, Department of Computing and Software, McMaster University, Hamilton, Ontario, Canada

Download: [PDF]

Entry Submitted: 10/19/2006
Entry Accepted: 10/19/2006
Entry Last Modified: 10/19/2006

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society