  We present and evaluate new techniques for designing algorithm portfolios. In
our view, the problem has both a scheduling aspect and a machine learning
aspect. Prior work has largely addressed one of the two aspects in isolation.
Building on recent work on the scheduling aspect of the problem, we present a
technique that addresses both aspects simultaneously and has attractive
theoretical guarantees. Experimentally, we show that this technique can be used
to improve the performance of state-of-the-art algorithms for Boolean
satisfiability, zero-one integer programming, and A.I. planning.
