The Network Simplex method works much faster than the traditional Simplex method for min/max flow problems. However, the Simplex algorithm struggles to handle the Klee-Minty cube because most pivoting rules don’t account for the shape of the polytope, and because of this it is shown that the Simplex algorithm is an exponential time algorithm, not a polynomial time algorithm.
However, this has had me thinking about the implications this has on the Network Simplex algorithm. Thus for anyone who knows more on worst-time formulations, my question is this:
Does there exist a graph, or a property of a graph, that shows that the Network Simplex method is an exponential time algorithm in a similar vein as the Klee-Minty cube showed that the Simplex method is exponential? (In that the Network Simplex method takes the “longest-path” to solve the min/max flow problem by taking a route that deploys the most amount of arc exchanges)
I’ve reached out to a few of my professors about this, and they had no answer and it’s had them really curious too, and I’ve looked and looked around on Google Scholar and such and couldn’t find any research articles on it, so I’m at a loss
In [1], the author gives a family of transportation problems with an exponential behaviour for the number of pivots in the simplex algorithm. If the scaling algorithm of Orlin is used, then it only takes polynomial time, since this algorithm is proved to be strongly polynomial.
[1]: Zadeh, Norman, A bad network problem for the simplex method and other minimum cost flow algorithms, Math. Program. 5, 255-266 (1973). ZBL0287.90030.