Comparing Methods

It should be clear that a comparison of methods must be based on empirical evaluation rather than on theoretical.

Assume that we apply a probabilistic method M to a problem P. We can see this as a mapping from (M,P) --> (E,m,q), where E is the effort applied and q is the probability that some minimum m is reached.

Assume that two methods are applied and that the same minimum is achieved. This gives

      (M1,P) --->(E1,m,q1)
      (M2,P) --->(E2,m,q2)

If Ei < Ej and qi > qj then obviously Mi is better than Mj for this problem. However, if we have that Ei < Ej and qi < qj then neither dominates the other and no conclusion about which is better can be made.

Because the results may vary depending on P and the levels of E and q a conclusive decision about the superiority of one method over another needs a lot of computations. Further, if also m varies and one method obtains a better solution but with much smaller probability with the same effort, which is then better?