# Is there any other algorithm whose worst-case running time is exponential meanwhile it works very well in practice other than Simplex Algorithm?

We generally call an algorithm "good algorithm" if it's runnning time is polynomial in the worst-case. But in some cases (for example Simplex algorithm), eventhough the worst-case of the algorithm is exponential, it could work very well in practice.

Are there any (deterministic) examples to this situatation other than Simplex algorithm?

The $k$-means algorithm for clustering is provably exponential even in the plane, but it works very well in practice.

Modern SAT solving algorithms are able to solve most instances quite fast, even though the worst case running time is, of course, exponential. In this case, however, the practical speed is more of a result of years of algorithm engineering, rather than that of a single elegant algorithm. While I've understood that conflict driven clause learning caused a major jump in the performance of SAT solvers, the later improvements are have often been achieved by a clever use of various heuristics in the algorithms.

• The other factor is that people generally only use them on problems which are amenable to CDCL based solving. It is very easy to run into problems where SAT solvers don't work, but people don't use SAT solvers on those problems for obvious reasons. Jul 22 '20 at 5:16

Hindley-Milner type inference is EXPTIME-complete, but on the programs people typically write it is pretty close to linear.

• Isn't this a bit different though? My recollection is that we could characterize a necessary condition for Hindley-Milner performing badly (deeply nested lets) and so the reason HM is good in practice is that this nesting is, in practice, bounded pretty low (usually we indent more as we go deeper into let bindings and get nervous as we head towards the rightmost edge of the screen...) Granted, I have made this claim from memory before and I was most recently unable to recover the reference for it. Nov 18 '10 at 16:10
• No, that's not a necessary condition. You can give a sequence of let-bindings (with no nesting!) such that it squares the size of the inferred type with each additional entry in the sequence. See cstheory.stackexchange.com/questions/2428/… for an example. Nov 18 '10 at 17:52
• The example is in SML, and I am more familiar with OCaml's way of doing things, but if that sequence of bindings were "let"s, then I think they would be nested. It is only because they define global functions that they are not, but there is an implicit nesting going on here: A given definition has access to all the definitions above it and none of those below.
– amnn
Apr 20 '16 at 20:36
• @amnn: The nesting referred to was nesting lets in the form being bound -- i.e., let z = (let y = e in e') in e'' as opposed to than let y = e in let z = e' in e''. Apr 21 '16 at 9:58

Brendan McKay's nauty (No AUTomorphisms, Yes?) program solves the canonical labeling problem of graphs (simultaneously solving the Graph Isomorphism and Graph Automorphism problems) and has exponential worst-case performance (Miyazaki, 1996). However, it works very quickly for most graphs, especially those with a few automorphisms.

Specifically, the algorithm begins by partitioning the vertices by degree, then by the degree between each part. When this process stabilizes, a choice must be made to distinguish a vertex in a non-trivial part, and this leads to the exponential behavior. In most graphs, the depth of this branching procedure is small.

• I thought that nauty also used some randomness to help in refinement? In that case, this might be very analogous to the simplex algorithm (although there's not obviously a notion of smoothed analysis for graph isomorphism). Nov 18 '10 at 16:52
• It doesn't use randomness, since it needs to make a consistent canonical labeling. However, it can use a custom-built vertex-invariant procedure in order to help partition the vertices. Sometimes this invariant looks random how it was produced (frequently, it's a complicated function on distance-degree sequences), but that's just to reduce collisions. Nov 18 '10 at 17:08
• This vertex-invariant can be compared to the anti-cycling rules of the simplex algorithm. Nov 18 '10 at 17:09

Several algorithms for simple stochastic games work well in practice, even though they have exponential worst-case running times. Of course, this problem is in some sense related to linear programming, although it is not known to be in polynomial time.

There's an algorithm for finding mixed Nash equilibria that's similar to the simplex algorithm for LPs. (I forget the name.) It has exponential worst-case complexity, but I have a vague memory that it often behaves well in practice.

• Do you mean the Lemke-Howson algorithm? Feb 2 '11 at 20:57

Bin packing (many variants) is a problem whose complexity is known to be NP-hard:

http://en.wikipedia.org/wiki/Bin_packing_problem

However, many heuristics when applied to "practical" versions do very well. For 1-dimensional bin packing some of these heuristics, like first-fit; first-fit decreasing; best-fit; best-fit decreasing are very appealing as topics to show students. Students often can discover some of the basic heuristics for themselves.

• There are many examples evenif the problem is NP-complete, simple algortihms can deal with it.Especially with approximation algorithms. But I am actually looking for exponential-time algorithms, your example is related to a hard problem which is easy to solve with simple algorithms. Maybe there is an exponential time algorithm to solve Bin packing (or another problem) exactly; and in practice it takes polynomial time. Nov 18 '10 at 22:43

The persistence algorithm (orig. from Edelsbrunner-Letscher-Zomorodian, with plenty of variations since) is worst case cubic, but seems from experimentation to usually run in linear time.