Abstract

Perturbation-based heuristics for the median string problem performs successive refinements to an incumbent solution. Perturbations can be applied (i) one by one or (ii) multiple at a time. Algorithms in (i) seem to converge to noticeable best quality solutions but are much slower than those in (ii). In this paper, we proposed an algorithm performing several edit operations at a time with a better trade-off between quality and execution time. A profuse experimental evaluation suggests our approach can converge to much better solutions than former algorithms in (ii), even comparable with (i) in some cases. In counterpart, it is much faster than those in (i) but slower than those in (ii).