9
$\begingroup$

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?

$\endgroup$
13
$\begingroup$

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.

$\endgroup$
13
$\begingroup$

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

$\endgroup$
13
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Rob Simmons Nov 18 '10 at 16:10
  • 2
    $\begingroup$ 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. $\endgroup$ – Neel Krishnaswami Nov 18 '10 at 17:52
  • $\begingroup$ 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. $\endgroup$ – amnn Apr 20 '16 at 20:36
  • 1
    $\begingroup$ @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''. $\endgroup$ – Neel Krishnaswami Apr 21 '16 at 9:58
9
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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). $\endgroup$ – Joshua Grochow Nov 18 '10 at 16:52
  • 1
    $\begingroup$ 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. $\endgroup$ – Derrick Stolee Nov 18 '10 at 17:08
  • 1
    $\begingroup$ This vertex-invariant can be compared to the anti-cycling rules of the simplex algorithm. $\endgroup$ – Derrick Stolee Nov 18 '10 at 17:09
4
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Do you mean the Lemke-Howson algorithm? $\endgroup$ – Rahul Savani Feb 2 '11 at 20:57
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Arman Nov 18 '10 at 22:43
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.