11
$\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?

Improve this question
$\endgroup$
1

8 Answers 8

Reset to default
15
$\begingroup$

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

Improve this answer
$\endgroup$
14
$\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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Antimony
    Commented Jul 22, 2020 at 5:16
13
$\begingroup$

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

Improve this answer
$\endgroup$
4
  • 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
    Commented Nov 18, 2010 at 16:10
  • 3
    $\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
    Commented Nov 18, 2010 at 17:52
  • 1
    $\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
    Commented Apr 20, 2016 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
    Commented Apr 21, 2016 at 9:58
10
$\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.

Improve this answer
$\endgroup$
3
  • $\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
    Commented Nov 18, 2010 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
    Commented Nov 18, 2010 at 17:08
  • 1
    $\begingroup$ This vertex-invariant can be compared to the anti-cycling rules of the simplex algorithm. $\endgroup$
    – Derrick Stolee
    Commented Nov 18, 2010 at 17:09
5
$\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.

Improve this answer
$\endgroup$
1
2
$\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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Do you mean the Lemke-Howson algorithm? $\endgroup$
    – Rahul Savani
    Commented Feb 2, 2011 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.

Improve this answer
$\endgroup$
1
  • $\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
    Commented Nov 18, 2010 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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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