On Maximum Speedup Ratio of Restart Algorithm Portfolios.

ALGORITHMS; ELECTRONIC portfolios; LITERATURE reviews; MATHEMATICAL optimization; HYPOTHESIS; MATHEMATICAL analysis

We discuss two possible parallel strategies for randomized restart algorithms. Given a set of available algorithms, one can either choose the best performing algorithm and run its multiple copies in parallel (single algorithm portfolio) or choose some subset of algorithms to run in parallel (mixed algorithm portfolio). It has been previously shown that the latter approach may provide better results computationally. In this paper, we provide theoretical investigation of the extent of such improvement generalizing some of the known results from the literature. In particular, we estimate the computational value of mixing randomized restart algorithms with different properties. Under some mild assumptions, we prove that in the best case the mixed algorithm portfolio may perform approximately up to 1.58 times faster than the best single algorithm portfolio. We also show that the obtained upper bound is sharp. Furthermore, the constructive proof of the main result allows us to characterize algorithms that are likely to form an effective mixed algorithm portfolio. [ABSTRACT FROM AUTHOR]

Copyright of INFORMS Journal on Computing is the property of INFORMS: Institute for Operations Research and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)