<p>Amenta and Ziegler proved that all currently-known constructions of exponential-time instances for simplex follow a particular structure that they call "deformed products":</p>

<blockquote>
  <p><a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.45.5072">Deformed Products and Maximal Shadows of Polytopes</a> by Amenta and Ziegler</p>
</blockquote>

<p>However, 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:</p>

<ol>
<li>Klee and Minty found the first exponential-time example.</li>
<li>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.</li>
<li>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.</li>
</ol>

CC BY-SA 2.5
2010-10-27T18:43:30.233Z
I always love sociological answers to math question ;). Thanks for the answer! I will take a closer look at AmentaZiegler1996, do you know of results since '96 that work well on deformed products? I found a paper by Norman Zadeh (from 1980 and 2009) that even in the '80s version [ http://www.stanford.edu/group/SOL/reports/OR-80-27.pdf ] mentions overcoming the deformed product construction.
Artem Kaznatcheev
CC BY-SA 2.5
2010-10-28T05:12:11.700Z
"Deformed product" was clearly an intuitive notion in the LP community decades before Nina and Gunter formalized it.  Certainly that's an accurate description of the Klee-Minty cubes!
Jeffε
CC BY-SA 2.5
2010-10-28T05:18:11.133Z
See also Matoušek and Szabo's exponential lower bounds for RANDOM EDGE on "abstract cubes", which can be seen as combinatorial cousins of Amenta and Ziegler's deformed products: http://portal.acm.org/citation.cfm?id=1033164
Jeffε
CC BY-SA 2.5
2010-10-27T06:37:53.653Z
2010-10-27T06:37:53.653Z
Ian
<p>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?</p>

<p>Results like <a href="http://arxiv.org/abs/cs/0111050v7">smoothed analysis</a> and the polynomial time algorithm <a href="http://portal.acm.org/citation.cfm?doid=1132516.1132524">extending it</a> 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.</p>

<p>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!</p>

CC BY-SA 2.5
2010-10-27T01:57:34.680Z
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
CC BY-SA 2.5
2010-10-27T02:09:09.210Z
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
CC BY-SA 2.5
2010-10-27T02:14:46.350Z
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
CC BY-SA 2.5
2010-10-27T03:26:44.660Z
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 
<cc.complexity-theory><reference-request><linear-programming><simplex>
The structure of pathological instances for simplex algorithms
Artem Kaznatcheev
# The structure of pathological instances for simplex algorithms

(Asked by: username_0 on 2010-10-27)

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](http://arxiv.org/abs/cs/0111050v7) and the polynomial time algorithm [extending it](http://portal.acm.org/citation.cfm?doid=1132516.1132524) 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!

**Tags:** cc.complexity-theory, reference-request, linear-programming, simplex
> **Comments:**
> **username_1**: 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.  
> **username_2**: 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?  
> **username_0**: 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?  
> **username_3**: 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.  

---

## 1 answers

### Answer by username_4 on 2010-10-27. Score: 18 | Accepted answer

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](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.45.5072) by Amenta and Ziegler

However, 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:

1. Klee and Minty found the first exponential-time example.
2. 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.
3. 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.

> **Comments:**
> **username_0**: I always love sociological answers to math question ;). Thanks for the answer! I will take a closer look at AmentaZiegler1996, do you know of results since '96 that work well on deformed products? I found a paper by Norman Zadeh (from 1980 and 2009) that even in the '80s version [ http://www.stanford.edu/group/SOL/reports/OR-80-27.pdf ] mentions overcoming the deformed product construction.  
> **username_5**: "Deformed product" was clearly an intuitive notion in the LP community decades before Nina and Gunter formalized it.  Certainly that's an accurate description of the Klee-Minty cubes!  
> **username_5**: See also Matoušek and Szabo's exponential lower bounds for RANDOM EDGE on "abstract cubes", which can be seen as combinatorial cousins of Amenta and Ziegler's deformed products: http://portal.acm.org/citation.cfm?id=1033164  

---

