Algorithm Portfolio Design: Theory vs. Practice
This addresses the challenge of solving computationally hard problems more efficiently for researchers and practitioners in fields like optimization and AI, though it appears incremental as it builds on existing portfolio theory.
The paper tackles the problem of improving computational efficiency for hard combinatorial search problems by using algorithm portfolios, showing that under certain conditions, portfolios can provide a dramatic computational advantage over traditional methods.
Stochastic algorithms are among the best for solving computationally hard search and reasoning problems. The runtime of such procedures is characterized by a random variable. Different algorithms give rise to different probability distributions. One can take advantage of such differences by combining several algorithms into a portfolio, and running them in parallel or interleaving them on a single processor. We provide a detailed evaluation of the portfolio approach on distributions of hard combinatorial search problems. We show under what conditions the protfolio approach can have a dramatic computational advantage over the best traditional methods.