• New techniques for algorithm portfolio design.  An algorithm portfolio is a schedule for interleaving the execution of several algorithms and periodically restarting them with a fresh random seed. Doing so can improve the average-case running time, for example if each algorithm has a few rare problem instances on which its running time is very large.
  
  At AAAI 2007 I had two papers that present new techniques for designing algorithm portfolios, both in offline and online settings. One is about designing task-switching schedules for interleaving the execution of multiple deterministic algorithms, and the other is about designing restart schedules for randomized algorithms. Further developments are described in the following NIPS 2008 paper and the following UAI 2008 paper.
  
  
• The max k-armed bandit problem.  Suppose you are in a casino with k slot machines. Each machine has an arm that, when pulled, returns a payoff drawn independently at random from a fixed (but unknown) distribution. Given n tokens, your goal is to maximize the highest payoff received from any single pull.
  
  In my AAAI 2006 paper, I present a no-regret algorithm for the case when each arm draws payoff from a generalized extreme value (GEV) distribution. In my CP 2006 paper, I present a different algorithm which requires weaker distributional assumptions and is effective at selecting among heuristics for the RCPSP/max, an NP-hard scheduling problem.
  
  
• Understanding random instances of the job shop scheduling problem.  I've obtained a number of theoretical and experimental results concerning backbone size, the quality of randomly-generated schedules, and the "big valley" distribution of local optima in random instances of the job shop scheduling problem. For more details, see my 2006 JAIR article and the earlier ICAPS 2005 conference paper.

Selected Publications by Topic

Algorithm Portfolios, etc.

New Techniques for Algorithm Portfolio Design
with Stephen Smith, in Proceedings of the Twenty-Fourth Conference on Uncertainty in Artificial Intelligence (UAI 2008)
[Paper]

An Online Algorithm for Maximizing Submodular Functions
with Daniel Golovin, at NIPS 2008.
[Paper] [Longer technical report]

Combining Multiple Heuristics Online
with Daniel Golovin and Stephen Smith, in Proceedings of the Twenty-Second Conference on Artificial Intelligence (AAAI 2007)
[Paper] [Slides (PDF,QuickTime)]

Restart Schedules for Ensembles of Problem Instances
with Daniel Golovin and Stephen Smith, in Proceedings of the Twenty-Second Conference on Artificial Intelligence (AAAI 2007)
[Paper] [Slides (PDF,QuickTime)]

Using Decision Procedures Efficiently for Optimization
with Stephen Smith, in Proceedings of the Seventeenth International Conference on Automated Planning and Scheduling (ICAPS 2007)
[Paper] [Slides (PDF,QuickTime)]

The Max k-Armed Bandit Problem

A Simple Distribution-Free Approach to the Max k-Armed Bandit Problem
with Stephen Smith, in Proceedings of the Twelfth International Conference on Principles and Practice of Constraint Programming (CP 2006)
[Paper] [Slides]

An Asymptotically Optimal Algorithm for the Max k-Armed Bandit Problem
with Stephen Smith, in Proceedings of the Twenty-First National Conference on Artificial Intelligence (AAAI 2006)
[Paper] [Slides]
A preliminary version appeared as a CMU technical report.

Job Shop Scheduling

Exploiting the Power of Local Search in a Branch and Bound Algorithm for Job Shop Scheduling
with Stephen Smith, in Proceedings of the Sixteenth International Conference on Automated Planning and Scheduling (ICAPS 2006)
[Paper] [Slides]

How the Landscape of Random Job Shop Scheduling Instances Depends on the Ratio of Jobs to Machines
with Stephen Smith, in Journal of Artificial Intelligence Research 26
[Paper]
A preliminary version appeared as a CMU technical report.

Characterizing the Distribution of Low-Makespan Schedules in the Job Shop Scheduling Problem
with Stephen Smith, in Proceedings of the Fifteenth International Conference on Automated Planning and Scheduling (ICAPS 2005)
[Paper] [Slides]

Evolutionary Computation Theory

Upper Bounds on the Time and Space Complexity of Optimizing Additively Separable Functions
in Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2004)
[Paper] [Slides] [Source code, etc.]

Two Broad Classes of Functions for which a No Free Lunch Result Does Not Hold
in Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2003)
[Paper] [Slides]

Genetic Programming

Genetic Programming IV: Routine Human-Competitive Machine Intelligence
with John Koza, Martin Keane, Bill Mydlowec, Jessen Yu, and Guido Lanza, Kluwer Academic Publishers
[Description] [Chapter 1]

Evolving Inventions
with John Koza and Martin Keane, in Scientific American
[Abstract]

What's AI Done for Me Lately? Genetic Programming's Human-Competitive Results
with John Koza and Martin Keane, in IEEE Intelligent Systems
[Paper]

Automated Discovery of Numerical Approximation Formulae via Genetic Programming
with Lee Becker, in Genetic Programming and Evolvable Machines, 4(3):255-286
[Abstract]

The Root Causes of Code Growth in Genetic Programming
in Proceedings of EuroGP 2003
[Paper]

Automatic Synthesis using Genetic Programming of Improved PID Tuning Rules
with Martin Keane and John Koza, in Proceedings of the 2003 Intelligent Control Systems and Signal Processing Conference (ICONS 2003)
[Paper] [Slides]

Iterative Refinement of Computational Circuits using Genetic Programming
with Martin Keane and John Koza, in Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2002)
[Paper] [Slides]

Automatic Synthesis using Genetic Programming of an Improved General-Purpose Controller for Industrially-Representative Plants
with Martin Keane and John Koza, in Proceedings of the NASA/DoD Conference on Evolvable Hardware
[Paper]