As far as I understand, all know deterministic pivot rules for simplex algorithms have specific inputs on which the algorithm requires exponential time (or at least not polynomial) to find the optimum. Let us call these instances 'pathological' since usually (i.e. on most inputs) the simplex algorithm terminates quickly. I remember from my mathematical programming course that the standard examples of pathological instances for specific rules were highly structured. My general question is if this is an artifact of the specific examples, or a feature of pathological instances in general?Results like smoothed analysis and the polynomial time algorithm extending it rely on perturbing the input --- suggesting that the pathological examples are very special. Hence the intuition that the pathological instances are highly-structured does not seem that far fetched.Does anybody have any specific insights on this? Or some references to existing work? I have been specifically vague about what I mean by 'structured' to try to be as encompassing as possible, but suggestions on how to better pin down 'structured' would also be useful. Any advice or references are greatly appreciated!
The structure of pathological instances for simplex algorithms
cc.complexity theory;reference request;linear programming;simplex
Amenta and Ziegler proved that all currently-known constructions of exponential-time instances for simplex follow a particular structure that they call deformed products:Deformed Products and Maximal Shadows of Polytopes by Amenta and ZieglerHowever, I don't think there's any reason to believe that all bad instances for simplex have this structure.  This is probably just an artifact of the research process:Klee and Minty found the first exponential-time example.Other researchers looked and Klee and Minty's techniques and extended them to other pivot rules.  They naturally took the path of least resistance and followed the Klee-Minty cube as closely as possible.Once someone finds one bad example for a pivot rule, there's no incentive for people to look for more.  As a result, all the bad examples we know of have a similar structure.