SPEAKER: Matt Streeter
TIME: Wednesday 12-1pm, February 14, 2007
PLACE: NSH 1507
TITLE: Combining Multiple Heuristics in an Adversarial Online Setting
ABSTRACT:
Heuristics for solving NP-hard problems often have complementary strengths
and weaknesses. For example, algorithms developed by statistical physicists
are extremely fast at solving satisfiable random 3-CNF formulae, while
algorithms based on chronological backtracking are faster on unsatisfiable
and structured formulae. What if we could combine several heuristics into a
meta-heuristic with better mean running time, on-the-fly while solving a
sequence of problem instances? This talk presents some no-regret algorithms
that can be used to do exactly that.
Specifically, we consider the following online problem. We are given a pool
of (randomized) heuristics and are fed, one at a time, a sequence of
instances of some decision problem. To solve each instance, we may
interleave the execution of the heuristics according to an arbitrary schedule
and may periodically restart each heuristic with a fresh random seed. Our
goal is to be competitive with the best fixed schedule in hindsight, even in
a universe where the run length distribution of each heuristic on each
instance is governed by an adversary.
This talk is based on joint work with Daniel Golovin and Stephen Smith.