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.
February 16, 2007
Ryan Williams
1:30 PM, 1507 Newell-Simon Hall
Thesis Proposal
Title: Algorithms and Resource Requirements for Fundamental Problems
Abstract:
We establish more efficient methods for solving certain classes of NP-hard problems exactly, as well as methods for proving limitations on how quickly the same problems can be solved.
For example, in the Max-Cut problem, one is given a graph $G=(V,E)$ and integer $K$, and one wishes to determine if $G$ has a subset of vertices such that the number of edges leaving the subset is at least $K$. The trivial algorithm for Max-Cut runs in roughly $O(poly(n)\cdot 2^n)$ time, where $n$ is the number of vertices in $G$. Prior to our work, no better algorithm was known for the general case. Our results imply that Max-Cut can be solved in $O(\sqrt{3}^n) = O(1.74^n)$ time and space, yet Max-Cut cannot be solved in $O(n^{\sqrt{3}})$ time and $n^{o(1)}$ space.
Further study includes finding faster algorithms and proving larger limitations for these problems, as well as extending our techniques to counting versions of {\sf NP} problems. We have already extended some of our algorithms in this manner, and are currently working on how limitations can be proved.
Thesis Committee:
Manuel Blum, Chair
Ryan O’Donnell
Steven Rudich
Russell Impagliazzo, University of California, San Diego
Dieter van Melkebeek, University of Wisconsin, Madison
