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.