# The structure of pathological instances for simplex algorithms

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!

• I am not sure if I have understood your question, but the opposite of “structured” seems to be “random.” If a simplex algorithm with a certain pivoting rule is inefficient already for random instances (with high probability, according to some natural distribution), probably people are not interested in constructing a bad example for that particular pivoting rule because that particular pivoting rule is mostly useless. – Tsuyoshi Ito Oct 27 '10 at 1:57
• Are you asking: for a fixed pivoting rule, what is the probability that a random instance will be pathological? i.e. the average-case analysis of the algorithm? – Kaveh Oct 27 '10 at 2:09
• I am not asking for the probability that a random instance is pathological. I am really just asking if pathological instances have a special structure to them. As Tsuyoshi points out, I should really restrict it to 'good' pivot rules, whatever that means. Any suggestions on how to make this more clear? – Artem Kaznatcheev Oct 27 '10 at 2:14
• I believe a lot of pathological instances are cubes whose sides have been maliciously perturbed, but I looked at this long enough ago that my memory could be completely wrong. – Peter Shor Oct 27 '10 at 3:26