Simple linkage: Analysis of a threshold-accepting global optimization method

In a recent paper the authors introduced an infinite class of global optimization algorithms based upon random sampling from the feasible region and local searches started from selected sample points, based upon an acceptance/rejection criterion. All of the algorithms of that class possess strong theoretical properties.Here we analyze a member of that family, which, although being significantly simpler to implement and more efficient than the well known Multi-Level Single-Linkage algorithm, enjoys the same theoretical properties. It is shown here that, with very high probability, our method is able to discover from which points Multi-Level Single-Linkage will decide to start local search.